QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#793241#4237. Word Ladderlukamosiashvili#AC ✓16ms7004kbC++171.9kb2024-11-29 17:53:372024-11-29 17:53:37

Judging History

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

  • [2024-11-29 17:53:37]
  • 评测
  • 测评结果:AC
  • 用时:16ms
  • 内存:7004kb
  • [2024-11-29 17:53:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

vector <string> ans;

map <long long, bool> m;
long long xr[19];

int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    //n = 5000;
    //n = 5;

    xr[0] = 1;
    for(int i = 1; i <= 10; i++) xr[i] = xr[i - 1] * 26;

    string s = "aaaaaaaaaa";
    ans.push_back(s);

    while(ans.size() < n){
        //cout << ans.size() << s << "\n";
        bool did = 0;
        for(int j = 0; j < s.size(); j++){
            char CH = s[j];
            for(int ch = 0; ch < 26; ch++){
                s[j] = 'a' + ch;
                if(s == ans[0]) continue;

                long long hsh = 0;
                for(int i = 0; i < s.size(); i++){
                    hsh += xr[i] * (s[i] - 'a');
                }

                bool flag = 0;
                for(int i = 0; i < s.size(); i++){
                    if(m[hsh - xr[i] * (s[i] - 'a')]){
                        flag = 1;
                        break;
                    }
                }

                if(!flag){
                    ans.push_back(s);
                    did = 1;
                    //m[hsh - xr[j] * (s[j] - 'a')] = 1;
                    hsh -= xr[j] * (s[j] - 'a');
                    hsh += xr[j] * (CH - 'a');

                    char ca = s[j];
                    s[j] = CH;

                    for(int i = 0; i < s.size(); i++){
                        m[hsh - xr[i] * (s[i] - 'a')] = 1;
                    }

                    s[j] = ca;
                    CH = s[j];
                    break;
                }else{
                    s[j] = CH;
                }
            }
            //if(did) break;
        }

        if(!did) break;
    }

    for(int i = 0; i < n; i++){
        cout << ans[i] << "\n";
    }

    //cout << ans.size() << "\n";

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3620kb

input:

5

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa

result:

ok good solution

Test #2:

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

input:

3

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa

result:

ok good solution

Test #3:

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

input:

4

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa

result:

ok good solution

Test #4:

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

input:

6

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa

result:

ok good solution

Test #5:

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

input:

7

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa

result:

ok good solution

Test #6:

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

input:

8

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa

result:

ok good solution

Test #7:

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

input:

9

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa

result:

ok good solution

Test #8:

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

input:

10

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa
bbbbbbbbba

result:

ok good solution

Test #9:

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

input:

64

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa
bbbbbbbbba
bbbbbbbbbb
cbbbbbbbbb
cabbbbbbbb
caabbbbbbb
caaabbbbbb
caaaabbbbb
caaaaabbbb
caaaaaabbb
caaaaaaabb
caaaaaaaab
caaaaaaaac
daaaaaaaac
dbaaaaaaac
dbbaaaaaac
dbbbaaaaac
dbbbbaaaac
dbbbbbaaac
dbb...

result:

ok good solution

Test #10:

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

input:

51

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa
bbbbbbbbba
bbbbbbbbbb
cbbbbbbbbb
cabbbbbbbb
caabbbbbbb
caaabbbbbb
caaaabbbbb
caaaaabbbb
caaaaaabbb
caaaaaaabb
caaaaaaaab
caaaaaaaac
daaaaaaaac
dbaaaaaaac
dbbaaaaaac
dbbbaaaaac
dbbbbaaaac
dbbbbbaaac
dbb...

result:

ok good solution

Test #11:

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

input:

97

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa
bbbbbbbbba
bbbbbbbbbb
cbbbbbbbbb
cabbbbbbbb
caabbbbbbb
caaabbbbbb
caaaabbbbb
caaaaabbbb
caaaaaabbb
caaaaaaabb
caaaaaaaab
caaaaaaaac
daaaaaaaac
dbaaaaaaac
dbbaaaaaac
dbbbaaaaac
dbbbbaaaac
dbbbbbaaac
dbb...

result:

ok good solution

Test #12:

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

input:

100

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa
bbbbbbbbba
bbbbbbbbbb
cbbbbbbbbb
cabbbbbbbb
caabbbbbbb
caaabbbbbb
caaaabbbbb
caaaaabbbb
caaaaaabbb
caaaaaaabb
caaaaaaaab
caaaaaaaac
daaaaaaaac
dbaaaaaaac
dbbaaaaaac
dbbbaaaaac
dbbbbaaaac
dbbbbbaaac
dbb...

result:

ok good solution

Test #13:

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

input:

1000

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa
bbbbbbbbba
bbbbbbbbbb
cbbbbbbbbb
cabbbbbbbb
caabbbbbbb
caaabbbbbb
caaaabbbbb
caaaaabbbb
caaaaaabbb
caaaaaaabb
caaaaaaaab
caaaaaaaac
daaaaaaaac
dbaaaaaaac
dbbaaaaaac
dbbbaaaaac
dbbbbaaaac
dbbbbbaaac
dbb...

result:

ok good solution

Test #14:

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

input:

1001

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa
bbbbbbbbba
bbbbbbbbbb
cbbbbbbbbb
cabbbbbbbb
caabbbbbbb
caaabbbbbb
caaaabbbbb
caaaaabbbb
caaaaaabbb
caaaaaaabb
caaaaaaaab
caaaaaaaac
daaaaaaaac
dbaaaaaaac
dbbaaaaaac
dbbbaaaaac
dbbbbaaaac
dbbbbbaaac
dbb...

result:

ok good solution

Test #15:

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

input:

1024

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa
bbbbbbbbba
bbbbbbbbbb
cbbbbbbbbb
cabbbbbbbb
caabbbbbbb
caaabbbbbb
caaaabbbbb
caaaaabbbb
caaaaaabbb
caaaaaaabb
caaaaaaaab
caaaaaaaac
daaaaaaaac
dbaaaaaaac
dbbaaaaaac
dbbbaaaaac
dbbbbaaaac
dbbbbbaaac
dbb...

result:

ok good solution

Test #16:

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

input:

1025

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa
bbbbbbbbba
bbbbbbbbbb
cbbbbbbbbb
cabbbbbbbb
caabbbbbbb
caaabbbbbb
caaaabbbbb
caaaaabbbb
caaaaaabbb
caaaaaaabb
caaaaaaaab
caaaaaaaac
daaaaaaaac
dbaaaaaaac
dbbaaaaaac
dbbbaaaaac
dbbbbaaaac
dbbbbbaaac
dbb...

result:

ok good solution

Test #17:

score: 0
Accepted
time: 12ms
memory: 7004kb

input:

5000

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa
bbbbbbbbba
bbbbbbbbbb
cbbbbbbbbb
cabbbbbbbb
caabbbbbbb
caaabbbbbb
caaaabbbbb
caaaaabbbb
caaaaaabbb
caaaaaaabb
caaaaaaaab
caaaaaaaac
daaaaaaaac
dbaaaaaaac
dbbaaaaaac
dbbbaaaaac
dbbbbaaaac
dbbbbbaaac
dbb...

result:

ok good solution

Test #18:

score: 0
Accepted
time: 16ms
memory: 6956kb

input:

4999

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa
bbbbbbbbba
bbbbbbbbbb
cbbbbbbbbb
cabbbbbbbb
caabbbbbbb
caaabbbbbb
caaaabbbbb
caaaaabbbb
caaaaaabbb
caaaaaaabb
caaaaaaaab
caaaaaaaac
daaaaaaaac
dbaaaaaaac
dbbaaaaaac
dbbbaaaaac
dbbbbaaaac
dbbbbbaaac
dbb...

result:

ok good solution

Test #19:

score: 0
Accepted
time: 13ms
memory: 6456kb

input:

4096

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa
bbbbbbbbba
bbbbbbbbbb
cbbbbbbbbb
cabbbbbbbb
caabbbbbbb
caaabbbbbb
caaaabbbbb
caaaaabbbb
caaaaaabbb
caaaaaaabb
caaaaaaaab
caaaaaaaac
daaaaaaaac
dbaaaaaaac
dbbaaaaaac
dbbbaaaaac
dbbbbaaaac
dbbbbbaaac
dbb...

result:

ok good solution

Test #20:

score: 0
Accepted
time: 4ms
memory: 6340kb

input:

4097

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa
bbbbbbbbba
bbbbbbbbbb
cbbbbbbbbb
cabbbbbbbb
caabbbbbbb
caaabbbbbb
caaaabbbbb
caaaaabbbb
caaaaaabbb
caaaaaaabb
caaaaaaaab
caaaaaaaac
daaaaaaaac
dbaaaaaaac
dbbaaaaaac
dbbbaaaaac
dbbbbaaaac
dbbbbbaaac
dbb...

result:

ok good solution

Test #21:

score: 0
Accepted
time: 9ms
memory: 6400kb

input:

4098

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa
bbbbbbbbba
bbbbbbbbbb
cbbbbbbbbb
cabbbbbbbb
caabbbbbbb
caaabbbbbb
caaaabbbbb
caaaaabbbb
caaaaaabbb
caaaaaaabb
caaaaaaaab
caaaaaaaac
daaaaaaaac
dbaaaaaaac
dbbaaaaaac
dbbbaaaaac
dbbbbaaaac
dbbbbbaaac
dbb...

result:

ok good solution

Test #22:

score: 0
Accepted
time: 12ms
memory: 6216kb

input:

3751

output:

aaaaaaaaaa
baaaaaaaaa
bbaaaaaaaa
bbbaaaaaaa
bbbbaaaaaa
bbbbbaaaaa
bbbbbbaaaa
bbbbbbbaaa
bbbbbbbbaa
bbbbbbbbba
bbbbbbbbbb
cbbbbbbbbb
cabbbbbbbb
caabbbbbbb
caaabbbbbb
caaaabbbbb
caaaaabbbb
caaaaaabbb
caaaaaaabb
caaaaaaaab
caaaaaaaac
daaaaaaaac
dbaaaaaaac
dbbaaaaaac
dbbbaaaaac
dbbbbaaaac
dbbbbbaaac
dbb...

result:

ok good solution