QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#98969#4237. Word LadderZomara#AC ✓105ms3932kbC++201.8kb2023-04-21 03:52:182023-04-21 03:52:19

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 03:52:19]
  • 评测
  • 测评结果:AC
  • 用时:105ms
  • 内存:3932kb
  • [2023-04-21 03:52:18]
  • 提交

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)
{
    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: 3480kb

input:

5

output:

aaaaaaaaaa
yaaaaaaaaa
yxaaaaaaaa
yxyaaaaaaa
yxyhaaaaaa

result:

ok good solution

Test #2:

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

input:

3

output:

aaaaaaaaaa
uaaaaaaaaa
ubaaaaaaaa

result:

ok good solution

Test #3:

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

input:

4

output:

aaaaaaaaaa
iaaaaaaaaa
iyaaaaaaaa
iybaaaaaaa

result:

ok good solution

Test #4:

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

input:

6

output:

aaaaaaaaaa
maaaaaaaaa
mnaaaaaaaa
mnnaaaaaaa
mnnnaaaaaa
mnnnvaaaaa

result:

ok good solution

Test #5:

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

input:

7

output:

aaaaaaaaaa
saaaaaaaaa
smaaaaaaaa
smvaaaaaaa
smvraaaaaa
smvrhaaaaa
smvrhxaaaa

result:

ok good solution

Test #6:

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

input:

8

output:

aaaaaaaaaa
vaaaaaaaaa
vwaaaaaaaa
vwzaaaaaaa
vwzvaaaaaa
vwzvlaaaaa
vwzvluaaaa
vwzvlukaaa

result:

ok good solution

Test #7:

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

input:

9

output:

aaaaaaaaaa
laaaaaaaaa
liaaaaaaaa
linaaaaaaa
linqaaaaaa
linqcaaaaa
linqcpaaaa
linqcpqaaa
linqcpqiaa

result:

ok good solution

Test #8:

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

input:

10

output:

aaaaaaaaaa
zaaaaaaaaa
zyaaaaaaaa
zybaaaaaaa
zybraaaaaa
zybrvaaaaa
zybrvraaaa
zybrvrnaaa
zybrvrnlaa
zybrvrnlqa

result:

ok good solution

Test #9:

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

input:

64

output:

aaaaaaaaaa
haaaaaaaaa
hoaaaaaaaa
hohaaaaaaa
hohmaaaaaa
hohmzaaaaa
hohmzpaaaa
hohmzpoaaa
hohmzpofaa
hohmzpofra
hohmzpofrw
johmzpofrw
jghmzpofrw
jgymzpofrw
jgyqzpofrw
jgyqgpofrw
jgyqggofrw
jgyqggbfrw
jgyqggbhrw
jgyqggbhjw
jgyqggbhja
lgyqggbhja
lsyqggbhja
lsiqggbhja
lsiyggbhja
lsiypgbhja
lsiyphbhja
lsi...

result:

ok good solution

Test #10:

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

input:

51

output:

aaaaaaaaaa
naaaaaaaaa
nsaaaaaaaa
nsgaaaaaaa
nsgsaaaaaa
nsgsraaaaa
nsgsrmaaaa
nsgsrmzaaa
nsgsrmzeaa
nsgsrmzeoa
nsgsrmzeol
dsgsrmzeol
dvgsrmzeol
dvksrmzeol
dvkprmzeol
dvkpmmzeol
dvkpmnzeol
dvkpmnteol
dvkpmntkol
dvkpmntktl
dvkpmntkts
gvkpmntkts
glkpmntkts
glfpmntkts
glfzmntkts
glfzuntkts
glfzujtkts
glf...

result:

ok good solution

Test #11:

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

input:

97

output:

aaaaaaaaaa
eaaaaaaaaa
eiaaaaaaaa
eiqaaaaaaa
eiqvaaaaaa
eiqvfaaaaa
eiqvfyaaaa
eiqvfyjaaa
eiqvfyjdaa
eiqvfyjdua
eiqvfyjdup
liqvfyjdup
lmqvfyjdup
lmivfyjdup
lmipfyjdup
lmippyjdup
lmippwjdup
lmippwgdup
lmippwgmup
lmippwgmhp
lmippwgmhr
gmippwgmhr
gfippwgmhr
gfnppwgmhr
gfnvpwgmhr
gfnvhwgmhr
gfnvhogmhr
gfn...

result:

ok good solution

Test #12:

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

input:

100

output:

aaaaaaaaaa
taaaaaaaaa
thaaaaaaaa
thkaaaaaaa
thklaaaaaa
thklsaaaaa
thklsdaaaa
thklsduaaa
thklsduvaa
thklsduvha
thklsduvhl
vhklsduvhl
vkklsduvhl
vkplsduvhl
vkptsduvhl
vkptmduvhl
vkptmxuvhl
vkptmxevhl
vkptmxeihl
vkptmxeixl
vkptmxeixz
ikptmxeixz
ixptmxeixz
ixftmxeixz
ixfgmxeixz
ixfgfxeixz
ixfgfkeixz
ixf...

result:

ok good solution

Test #13:

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

input:

1000

output:

aaaaaaaaaa
waaaaaaaaa
wnaaaaaaaa
wnwaaaaaaa
wnwvaaaaaa
wnwvzaaaaa
wnwvzjaaaa
wnwvzjgaaa
wnwvzjgnaa
wnwvzjgnya
wnwvzjgnyl
qnwvzjgnyl
qzwvzjgnyl
qzuvzjgnyl
qzuczjgnyl
qzuckjgnyl
qzuckkgnyl
qzuckkhnyl
qzuckkhdyl
qzuckkhdsl
qzuckkhdsk
azuckkhdsk
acuckkhdsk
aczckkhdsk
aczzkkhdsk
aczzukhdsk
aczzuchdsk
acz...

result:

ok good solution

Test #14:

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

input:

1001

output:

aaaaaaaaaa
gaaaaaaaaa
gzaaaaaaaa
gznaaaaaaa
gznbaaaaaa
gznbmaaaaa
gznbmmaaaa
gznbmmxaaa
gznbmmxdaa
gznbmmxdpa
gznbmmxdpl
dznbmmxdpl
dnnbmmxdpl
dndbmmxdpl
dndammxdpl
dndakmxdpl
dndakhxdpl
dndakhidpl
dndakhifpl
dndakhifxl
dndakhifxv
nndakhifxv
nvdakhifxv
nvlakhifxv
nvlfkhifxv
nvlfxhifxv
nvlfxaifxv
nvl...

result:

ok good solution

Test #15:

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

input:

1024

output:

aaaaaaaaaa
uaaaaaaaaa
uuaaaaaaaa
uubaaaaaaa
uubnaaaaaa
uubnzaaaaa
uubnzmaaaa
uubnzmvaaa
uubnzmveaa
uubnzmveua
uubnzmveuq
gubnzmveuq
gebnzmveuq
geinzmveuq
geilzmveuq
geilkmveuq
geilkcveuq
geilkcieuq
geilkciquq
geilkciqnq
geilkciqnz
ueilkciqnz
uyilkciqnz
uyulkciqnz
uyuvkciqnz
uyuviciqnz
uyuviliqnz
uyu...

result:

ok good solution

Test #16:

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

input:

1025

output:

aaaaaaaaaa
qaaaaaaaaa
qqaaaaaaaa
qqtaaaaaaa
qqtraaaaaa
qqtrsaaaaa
qqtrsmaaaa
qqtrsmvaaa
qqtrsmveaa
qqtrsmveda
qqtrsmvedy
xqtrsmvedy
xctrsmvedy
xclrsmvedy
xclxsmvedy
xclxtmvedy
xclxtzvedy
xclxtzsedy
xclxtzswdy
xclxtzswjy
xclxtzswjg
mclxtzswjg
mdlxtzswjg
mdextzswjg
mdebtzswjg
mdebkzswjg
mdebkoswjg
mde...

result:

ok good solution

Test #17:

score: 0
Accepted
time: 105ms
memory: 3932kb

input:

5000

output:

aaaaaaaaaa
qaaaaaaaaa
qnaaaaaaaa
qntaaaaaaa
qntyaaaaaa
qntyjaaaaa
qntyjpaaaa
qntyjpkaaa
qntyjpkuaa
qntyjpkuda
qntyjpkudl
sntyjpkudl
swtyjpkudl
swryjpkudl
swrojpkudl
swrodpkudl
swrodwkudl
swrodwzudl
swrodwzcdl
swrodwzcgl
swrodwzcgs
owrodwzcgs
oirodwzcgs
oivodwzcgs
oivsdwzcgs
oivsuwzcgs
oivsuuzcgs
oiv...

result:

ok good solution

Test #18:

score: 0
Accepted
time: 104ms
memory: 3848kb

input:

4999

output:

aaaaaaaaaa
oaaaaaaaaa
ozaaaaaaaa
oztaaaaaaa
oztkaaaaaa
oztknaaaaa
oztkneaaaa
oztknenaaa
oztknenmaa
oztknenmza
oztknenmzc
kztknenmzc
kctknenmzc
kczknenmzc
kczunenmzc
kczuvenmzc
kczuvunmzc
kczuvuamzc
kczuvuafzc
kczuvuafqc
kczuvuafqi
bczuvuafqi
bazuvuafqi
baeuvuafqi
baezvuafqi
baezcuafqi
baezcaafqi
bae...

result:

ok good solution

Test #19:

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

input:

4096

output:

aaaaaaaaaa
paaaaaaaaa
pfaaaaaaaa
pftaaaaaaa
pfttaaaaaa
pfttlaaaaa
pfttlxaaaa
pfttlxfaaa
pfttlxfraa
pfttlxfrla
pfttlxfrli
yfttlxfrli
ymttlxfrli
ymxtlxfrli
ymxjlxfrli
ymxjexfrli
ymxjemfrli
ymxjemxrli
ymxjemxbli
ymxjemxbxi
ymxjemxbxh
kmxjemxbxh
kwxjemxbxh
kwbjemxbxh
kwbpemxbxh
kwbpimxbxh
kwbpitxbxh
kwb...

result:

ok good solution

Test #20:

score: 0
Accepted
time: 83ms
memory: 3756kb

input:

4097

output:

aaaaaaaaaa
oaaaaaaaaa
oxaaaaaaaa
oxkaaaaaaa
oxklaaaaaa
oxklqaaaaa
oxklqpaaaa
oxklqpmaaa
oxklqpmkaa
oxklqpmkja
oxklqpmkjj
rxklqpmkjj
rvklqpmkjj
rvmlqpmkjj
rvmzqpmkjj
rvmzjpmkjj
rvmzjsmkjj
rvmzjsukjj
rvmzjsuqjj
rvmzjsuqnj
rvmzjsuqnv
gvmzjsuqnv
gmmzjsuqnv
gmkzjsuqnv
gmksjsuqnv
gmksvsuqnv
gmksvcuqnv
gmk...

result:

ok good solution

Test #21:

score: 0
Accepted
time: 75ms
memory: 3756kb

input:

4098

output:

aaaaaaaaaa
maaaaaaaaa
mraaaaaaaa
mrkaaaaaaa
mrkjaaaaaa
mrkjoaaaaa
mrkjopaaaa
mrkjopgaaa
mrkjopgdaa
mrkjopgdca
mrkjopgdcg
xrkjopgdcg
xzkjopgdcg
xzejopgdcg
xzedopgdcg
xzednpgdcg
xzednkgdcg
xzednktdcg
xzednktocg
xzednktovg
xzednktovo
gzednktovo
ghednktovo
ghidnktovo
ghipnktovo
ghipsktovo
ghipsztovo
ghi...

result:

ok good solution

Test #22:

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

input:

3751

output:

aaaaaaaaaa
haaaaaaaaa
hmaaaaaaaa
hmgaaaaaaa
hmgvaaaaaa
hmgvqaaaaa
hmgvqoaaaa
hmgvqodaaa
hmgvqodlaa
hmgvqodlza
hmgvqodlzb
emgvqodlzb
eagvqodlzb
eazvqodlzb
eaziqodlzb
eazitodlzb
eazitedlzb
eazitexlzb
eazitextzb
eazitextob
eazitextoz
hazitextoz
hxzitextoz
hxlitextoz
hxlotextoz
hxlodextoz
hxlodsxtoz
hxl...

result:

ok good solution