QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#99009#4237. Word LadderZuqaAC ✓101ms3872kbC++201.8kb2023-04-21 08:35:302023-04-21 08:35:31

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-21 08:35:31]
  • 评测
  • 测评结果:AC
  • 用时:101ms
  • 内存:3872kb
  • [2023-04-21 08:35:30]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
typedef unsigned long long ull;

template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937_64 for long long
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());

set<string> st;

bool bad(string &s, string &prv)
{
if(s == prv)
        return true;
    string t = s;
    for(int i = 0; i < s.length(); i++)
    {
        for(char c = 'a'; c <= 'z'; c++)
        {
            t[i] = c;
            if(t == prv)
                continue;
            if(st.count(t))
                return true;
        }
        t[i] = s[i];
    }
    return false;
}

void doWork()
{
    int n;
    cin >> n;
    vector<string> v(n, "aaaaaaaaaa");

    st.insert(v[0]);
    int nxtChange = 0;
    for(int i = 1; i < n; i++)
    {
        string nxtString = v[i - 1];
        do
        {
            char nxtChar = (char) ('a' + rng() % 26);
            nxtString[nxtChange] = nxtChar;
        } while(bad(nxtString, v[i - 1]));

        nxtChange++, nxtChange %= 10;
        st.insert(nxtString);
        v[i] = nxtString;
    }

    for(auto &it: v)
        cout << it << '\n';
}

signed main()
{
    FIO
    int T = 1;
//    cin >> T;
    for(int i = 1; i <= T; i++)
        doWork();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3356kb

input:

5

output:

aaaaaaaaaa
oaaaaaaaaa
oeaaaaaaaa
oegaaaaaaa
oeghaaaaaa

result:

ok good solution

Test #2:

score: 0
Accepted
time: 2ms
memory: 3436kb

input:

3

output:

aaaaaaaaaa
faaaaaaaaa
fwaaaaaaaa

result:

ok good solution

Test #3:

score: 0
Accepted
time: 2ms
memory: 3360kb

input:

4

output:

aaaaaaaaaa
laaaaaaaaa
lbaaaaaaaa
lbpaaaaaaa

result:

ok good solution

Test #4:

score: 0
Accepted
time: 2ms
memory: 3356kb

input:

6

output:

aaaaaaaaaa
maaaaaaaaa
muaaaaaaaa
mutaaaaaaa
mutxaaaaaa
mutxvaaaaa

result:

ok good solution

Test #5:

score: 0
Accepted
time: 2ms
memory: 3392kb

input:

7

output:

aaaaaaaaaa
daaaaaaaaa
dbaaaaaaaa
dbbaaaaaaa
dbbuaaaaaa
dbbupaaaaa
dbbupqaaaa

result:

ok good solution

Test #6:

score: 0
Accepted
time: 2ms
memory: 3460kb

input:

8

output:

aaaaaaaaaa
xaaaaaaaaa
xtaaaaaaaa
xtfaaaaaaa
xtfdaaaaaa
xtfdlaaaaa
xtfdlfaaaa
xtfdlfiaaa

result:

ok good solution

Test #7:

score: 0
Accepted
time: 0ms
memory: 3472kb

input:

9

output:

aaaaaaaaaa
waaaaaaaaa
wvaaaaaaaa
wvdaaaaaaa
wvddaaaaaa
wvddwaaaaa
wvddwvaaaa
wvddwvzaaa
wvddwvzbaa

result:

ok good solution

Test #8:

score: 0
Accepted
time: 0ms
memory: 3460kb

input:

10

output:

aaaaaaaaaa
gaaaaaaaaa
guaaaaaaaa
gucaaaaaaa
guclaaaaaa
guclraaaaa
guclrbaaaa
guclrblaaa
guclrblxaa
guclrblxra

result:

ok good solution

Test #9:

score: 0
Accepted
time: 2ms
memory: 3500kb

input:

64

output:

aaaaaaaaaa
qaaaaaaaaa
qkaaaaaaaa
qktaaaaaaa
qktsaaaaaa
qktsjaaaaa
qktsjcaaaa
qktsjclaaa
qktsjclyaa
qktsjclyga
qktsjclygu
mktsjclygu
mntsjclygu
mnesjclygu
mneljclygu
mnelqclygu
mnelqglygu
mnelqgoygu
mnelqgopgu
mnelqgopcu
mnelqgopci
xnelqgopci
xqelqgopci
xqylqgopci
xqymqgopci
xqymvgopci
xqymvmopci
xqy...

result:

ok good solution

Test #10:

score: 0
Accepted
time: 2ms
memory: 3488kb

input:

51

output:

aaaaaaaaaa
caaaaaaaaa
cjaaaaaaaa
cjhaaaaaaa
cjhxaaaaaa
cjhxtaaaaa
cjhxtiaaaa
cjhxtiqaaa
cjhxtiqjaa
cjhxtiqjfa
cjhxtiqjfv
rjhxtiqjfv
rihxtiqjfv
ripxtiqjfv
riphtiqjfv
riphaiqjfv
riphanqjfv
riphanvjfv
riphanvtfv
riphanvtyv
riphanvtyf
oiphanvtyf
onphanvtyf
onvhanvtyf
onvcanvtyf
onvcynvtyf
onvcyxvtyf
onv...

result:

ok good solution

Test #11:

score: 0
Accepted
time: 0ms
memory: 3472kb

input:

97

output:

aaaaaaaaaa
baaaaaaaaa
bsaaaaaaaa
bswaaaaaaa
bswwaaaaaa
bswwbaaaaa
bswwbuaaaa
bswwbufaaa
bswwbufhaa
bswwbufhba
bswwbufhbu
vswwbufhbu
vpwwbufhbu
vptwbufhbu
vptdbufhbu
vptdfufhbu
vptdfmfhbu
vptdfmbhbu
vptdfmbxbu
vptdfmbxcu
vptdfmbxcb
gptdfmbxcb
gutdfmbxcb
guldfmbxcb
gullfmbxcb
gullnmbxcb
gullnxbxcb
gul...

result:

ok good solution

Test #12:

score: 0
Accepted
time: 3ms
memory: 3476kb

input:

100

output:

aaaaaaaaaa
caaaaaaaaa
cfaaaaaaaa
cfhaaaaaaa
cfhbaaaaaa
cfhbnaaaaa
cfhbnkaaaa
cfhbnkraaa
cfhbnkrvaa
cfhbnkrvga
cfhbnkrvgp
jfhbnkrvgp
jshbnkrvgp
jsebnkrvgp
jsexnkrvgp
jsexdkrvgp
jsexdcrvgp
jsexdctvgp
jsexdctrgp
jsexdctrwp
jsexdctrwz
vsexdctrwz
veexdctrwz
venxdctrwz
venqdctrwz
venqmctrwz
venqmvtrwz
ven...

result:

ok good solution

Test #13:

score: 0
Accepted
time: 19ms
memory: 3612kb

input:

1000

output:

aaaaaaaaaa
waaaaaaaaa
wjaaaaaaaa
wjxaaaaaaa
wjxkaaaaaa
wjxkoaaaaa
wjxkocaaaa
wjxkockaaa
wjxkocknaa
wjxkocknha
wjxkocknhi
ajxkocknhi
axxkocknhi
axckocknhi
axcuocknhi
axculcknhi
axculmknhi
axculmanhi
axculmaihi
axculmaici
axculmaicf
qxculmaicf
qfculmaicf
qfqulmaicf
qfqxlmaicf
qfqxrmaicf
qfqxrtaicf
qfq...

result:

ok good solution

Test #14:

score: 0
Accepted
time: 18ms
memory: 3468kb

input:

1001

output:

aaaaaaaaaa
haaaaaaaaa
hiaaaaaaaa
hiqaaaaaaa
hiqcaaaaaa
hiqchaaaaa
hiqchuaaaa
hiqchuyaaa
hiqchuybaa
hiqchuybta
hiqchuybtd
ziqchuybtd
znqchuybtd
znxchuybtd
znxjhuybtd
znxjouybtd
znxjojybtd
znxjojgbtd
znxjojgrtd
znxjojgrsd
znxjojgrsv
fnxjojgrsv
fuxjojgrsv
fubjojgrsv
fubbojgrsv
fubbqjgrsv
fubbqggrsv
fub...

result:

ok good solution

Test #15:

score: 0
Accepted
time: 18ms
memory: 3572kb

input:

1024

output:

aaaaaaaaaa
naaaaaaaaa
nvaaaaaaaa
nvraaaaaaa
nvriaaaaaa
nvrijaaaaa
nvrijbaaaa
nvrijbdaaa
nvrijbdbaa
nvrijbdbha
nvrijbdbhw
jvrijbdbhw
jorijbdbhw
jovijbdbhw
jovajbdbhw
jovaobdbhw
jovaosdbhw
jovaosibhw
jovaosihhw
jovaosihlw
jovaosihli
tovaosihli
thvaosihli
thbaosihli
thbwosihli
thbwwsihli
thbwwiihli
thb...

result:

ok good solution

Test #16:

score: 0
Accepted
time: 19ms
memory: 3548kb

input:

1025

output:

aaaaaaaaaa
iaaaaaaaaa
iqaaaaaaaa
iqraaaaaaa
iqrxaaaaaa
iqrxeaaaaa
iqrxekaaaa
iqrxekkaaa
iqrxekkeaa
iqrxekkeda
iqrxekkedu
rqrxekkedu
rwrxekkedu
rwfxekkedu
rwfmekkedu
rwfmtkkedu
rwfmtlkedu
rwfmtloedu
rwfmtlopdu
rwfmtlopzu
rwfmtlopzo
iwfmtlopzo
iofmtlopzo
ioumtlopzo
ioultlopzo
ioulvlopzo
ioulvbopzo
iou...

result:

ok good solution

Test #17:

score: 0
Accepted
time: 97ms
memory: 3852kb

input:

5000

output:

aaaaaaaaaa
caaaaaaaaa
chaaaaaaaa
chhaaaaaaa
chhcaaaaaa
chhcpaaaaa
chhcpyaaaa
chhcpymaaa
chhcpymdaa
chhcpymdja
chhcpymdjz
phhcpymdjz
pfhcpymdjz
pfycpymdjz
pfyrpymdjz
pfyrjymdjz
pfyrjrmdjz
pfyrjredjz
pfyrjrerjz
pfyrjrervz
pfyrjrervu
kfyrjrervu
ksyrjrervu
ksdrjrervu
ksdgjrervu
ksdgfrervu
ksdgfpervu
ksd...

result:

ok good solution

Test #18:

score: 0
Accepted
time: 101ms
memory: 3768kb

input:

4999

output:

aaaaaaaaaa
saaaaaaaaa
swaaaaaaaa
swlaaaaaaa
swlfaaaaaa
swlfwaaaaa
swlfwhaaaa
swlfwhlaaa
swlfwhlmaa
swlfwhlmxa
swlfwhlmxz
hwlfwhlmxz
hslfwhlmxz
hspfwhlmxz
hspnwhlmxz
hspnghlmxz
hspngvlmxz
hspngvpmxz
hspngvppxz
hspngvppaz
hspngvppav
yspngvppav
yppngvppav
yprngvppav
yprjgvppav
yprjivppav
yprjijppav
ypr...

result:

ok good solution

Test #19:

score: 0
Accepted
time: 81ms
memory: 3696kb

input:

4096

output:

aaaaaaaaaa
laaaaaaaaa
lraaaaaaaa
lrxaaaaaaa
lrxraaaaaa
lrxrfaaaaa
lrxrfiaaaa
lrxrfiwaaa
lrxrfiwwaa
lrxrfiwwoa
lrxrfiwwob
hrxrfiwwob
hhxrfiwwob
hhnrfiwwob
hhnmfiwwob
hhnmtiwwob
hhnmtcwwob
hhnmtciwob
hhnmtcibob
hhnmtcibfb
hhnmtcibfm
qhnmtcibfm
qjnmtcibfm
qjtmtcibfm
qjtntcibfm
qjtnccibfm
qjtncdibfm
qjt...

result:

ok good solution

Test #20:

score: 0
Accepted
time: 82ms
memory: 3788kb

input:

4097

output:

aaaaaaaaaa
haaaaaaaaa
hlaaaaaaaa
hlwaaaaaaa
hlwoaaaaaa
hlwooaaaaa
hlwoosaaaa
hlwoosxaaa
hlwoosxlaa
hlwoosxlka
hlwoosxlkr
elwoosxlkr
egwoosxlkr
egpoosxlkr
egpzosxlkr
egpzcsxlkr
egpzcaxlkr
egpzcawlkr
egpzcawxkr
egpzcawxyr
egpzcawxyh
ygpzcawxyh
yvpzcawxyh
yvzzcawxyh
yvzjcawxyh
yvzjfawxyh
yvzjfhwxyh
yvz...

result:

ok good solution

Test #21:

score: 0
Accepted
time: 82ms
memory: 3716kb

input:

4098

output:

aaaaaaaaaa
oaaaaaaaaa
oxaaaaaaaa
oxnaaaaaaa
oxnzaaaaaa
oxnzraaaaa
oxnzrfaaaa
oxnzrftaaa
oxnzrftxaa
oxnzrftxda
oxnzrftxde
xxnzrftxde
xmnzrftxde
xmczrftxde
xmcnrftxde
xmcnuftxde
xmcnudtxde
xmcnudcxde
xmcnudclde
xmcnudclhe
xmcnudclhm
vmcnudclhm
vkcnudclhm
vkanudclhm
vkayudclhm
vkaygdclhm
vkaygcclhm
vka...

result:

ok good solution

Test #22:

score: 0
Accepted
time: 73ms
memory: 3872kb

input:

3751

output:

aaaaaaaaaa
uaaaaaaaaa
ueaaaaaaaa
uecaaaaaaa
ueceaaaaaa
uecejaaaaa
uecejqaaaa
uecejqdaaa
uecejqdvaa
uecejqdvta
uecejqdvtx
kecejqdvtx
kgcejqdvtx
kgdejqdvtx
kgdwjqdvtx
kgdwaqdvtx
kgdwaedvtx
kgdwaejvtx
kgdwaejptx
kgdwaejpmx
kgdwaejpmm
ygdwaejpmm
yndwaejpmm
yntwaejpmm
yntsaejpmm
yntstejpmm
yntstqjpmm
ynt...

result:

ok good solution