QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#793241 | #4237. Word Ladder | lukamosiashvili# | AC ✓ | 16ms | 7004kb | C++17 | 1.9kb | 2024-11-29 17:53:37 | 2024-11-29 17:53:37 |
Judging History
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