QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#99573 | #4237. Word Ladder | Anwar_Gehad_Maghraby# | AC ✓ | 755ms | 5344kb | C++17 | 1.5kb | 2023-04-23 04:19:54 | 2023-04-23 04:19:55 |
Judging History
answer
/**
* author: MaGnsi0
* created: 22.04.2023 21:50:35
**/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin >> n;
string s(5, '*');
for (char c = 'a'; c <= 'j'; ++c) {
s[c - 'a'] = c;
}
set<string> s_;
s_.insert(s);
vector<string> ans;
ans.push_back(s);
function<void(string, int)> solve = [&](string t, int j) {
if ((int)ans.size() == n) {
for (int i = 0; i < n; ++i) {
cout << ans[i] << "\n";
}
exit(0);
}
for (int i = 0; i < 5; ++i) {
if (i == j) { continue; }
for (char c = 'z'; c >= 'a'; --c) {
if (c == t[i]) { continue; }
string x = t;
x[i] = c;
if (s_.count(x)) { continue; }
bool ok = true;
for (int k = 0; k < 5; ++k) {
for (char c_ = 'a'; c_ <= 'z'; ++c_) {
string y = x;
y[k] = c_;
if (y != t && s_.count(y)) {
ok = false;
}
}
}
if (ok == false) { continue; }
ans.push_back(x);
s_.insert(x);
solve(x, i);
ans.pop_back();
s_.erase(x);
}
}
};
solve(s, -1);
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3436kb
input:
5
output:
abcde zbcde zzcde yzcde yycde
result:
ok good solution
Test #2:
score: 0
Accepted
time: 1ms
memory: 3360kb
input:
3
output:
abcde zbcde zzcde
result:
ok good solution
Test #3:
score: 0
Accepted
time: 2ms
memory: 3344kb
input:
4
output:
abcde zbcde zzcde yzcde
result:
ok good solution
Test #4:
score: 0
Accepted
time: 2ms
memory: 3352kb
input:
6
output:
abcde zbcde zzcde yzcde yycde xycde
result:
ok good solution
Test #5:
score: 0
Accepted
time: 2ms
memory: 3356kb
input:
7
output:
abcde zbcde zzcde yzcde yycde xycde xxcde
result:
ok good solution
Test #6:
score: 0
Accepted
time: 2ms
memory: 3416kb
input:
8
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde
result:
ok good solution
Test #7:
score: 0
Accepted
time: 2ms
memory: 3444kb
input:
9
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde
result:
ok good solution
Test #8:
score: 0
Accepted
time: 2ms
memory: 3404kb
input:
10
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde vwcde
result:
ok good solution
Test #9:
score: 0
Accepted
time: 6ms
memory: 3476kb
input:
64
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde vwcde vvcde uvcde uucde tucde ttcde stcde sscde rscde rrcde qrcde qqcde pqcde ppcde opcde oocde nocde nncde mncde mmcde lmcde llcde klcde kkcde jkcde jjcde ijcde iicde hicde hhcde ghcde ggcde fgcde ffcde efcde eecde decde ddcde cdcde cccde bccde ...
result:
ok good solution
Test #10:
score: 0
Accepted
time: 0ms
memory: 3420kb
input:
51
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde vwcde vvcde uvcde uucde tucde ttcde stcde sscde rscde rrcde qrcde qqcde pqcde ppcde opcde oocde nocde nncde mncde mmcde lmcde llcde klcde kkcde jkcde jjcde ijcde iicde hicde hhcde ghcde ggcde fgcde ffcde efcde eecde decde ddcde cdcde cccde bccde ...
result:
ok good solution
Test #11:
score: 0
Accepted
time: 9ms
memory: 3440kb
input:
97
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde vwcde vvcde uvcde uucde tucde ttcde stcde sscde rscde rrcde qrcde qqcde pqcde ppcde opcde oocde nocde nncde mncde mmcde lmcde llcde klcde kkcde jkcde jjcde ijcde iicde hicde hhcde ghcde ggcde fgcde ffcde efcde eecde decde ddcde cdcde cccde bccde ...
result:
ok good solution
Test #12:
score: 0
Accepted
time: 10ms
memory: 3380kb
input:
100
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde vwcde vvcde uvcde uucde tucde ttcde stcde sscde rscde rrcde qrcde qqcde pqcde ppcde opcde oocde nocde nncde mncde mmcde lmcde llcde klcde kkcde jkcde jjcde ijcde iicde hicde hhcde ghcde ggcde fgcde ffcde efcde eecde decde ddcde cdcde cccde bccde ...
result:
ok good solution
Test #13:
score: 0
Accepted
time: 115ms
memory: 3756kb
input:
1000
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde vwcde vvcde uvcde uucde tucde ttcde stcde sscde rscde rrcde qrcde qqcde pqcde ppcde opcde oocde nocde nncde mncde mmcde lmcde llcde klcde kkcde jkcde jjcde ijcde iicde hicde hhcde ghcde ggcde fgcde ffcde efcde eecde decde ddcde cdcde cccde bccde ...
result:
ok good solution
Test #14:
score: 0
Accepted
time: 119ms
memory: 3860kb
input:
1001
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde vwcde vvcde uvcde uucde tucde ttcde stcde sscde rscde rrcde qrcde qqcde pqcde ppcde opcde oocde nocde nncde mncde mmcde lmcde llcde klcde kkcde jkcde jjcde ijcde iicde hicde hhcde ghcde ggcde fgcde ffcde efcde eecde decde ddcde cdcde cccde bccde ...
result:
ok good solution
Test #15:
score: 0
Accepted
time: 122ms
memory: 3764kb
input:
1024
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde vwcde vvcde uvcde uucde tucde ttcde stcde sscde rscde rrcde qrcde qqcde pqcde ppcde opcde oocde nocde nncde mncde mmcde lmcde llcde klcde kkcde jkcde jjcde ijcde iicde hicde hhcde ghcde ggcde fgcde ffcde efcde eecde decde ddcde cdcde cccde bccde ...
result:
ok good solution
Test #16:
score: 0
Accepted
time: 122ms
memory: 3792kb
input:
1025
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde vwcde vvcde uvcde uucde tucde ttcde stcde sscde rscde rrcde qrcde qqcde pqcde ppcde opcde oocde nocde nncde mncde mmcde lmcde llcde klcde kkcde jkcde jjcde ijcde iicde hicde hhcde ghcde ggcde fgcde ffcde efcde eecde decde ddcde cdcde cccde bccde ...
result:
ok good solution
Test #17:
score: 0
Accepted
time: 753ms
memory: 5340kb
input:
5000
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde vwcde vvcde uvcde uucde tucde ttcde stcde sscde rscde rrcde qrcde qqcde pqcde ppcde opcde oocde nocde nncde mncde mmcde lmcde llcde klcde kkcde jkcde jjcde ijcde iicde hicde hhcde ghcde ggcde fgcde ffcde efcde eecde decde ddcde cdcde cccde bccde ...
result:
ok good solution
Test #18:
score: 0
Accepted
time: 755ms
memory: 5344kb
input:
4999
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde vwcde vvcde uvcde uucde tucde ttcde stcde sscde rscde rrcde qrcde qqcde pqcde ppcde opcde oocde nocde nncde mncde mmcde lmcde llcde klcde kkcde jkcde jjcde ijcde iicde hicde hhcde ghcde ggcde fgcde ffcde efcde eecde decde ddcde cdcde cccde bccde ...
result:
ok good solution
Test #19:
score: 0
Accepted
time: 605ms
memory: 5016kb
input:
4096
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde vwcde vvcde uvcde uucde tucde ttcde stcde sscde rscde rrcde qrcde qqcde pqcde ppcde opcde oocde nocde nncde mncde mmcde lmcde llcde klcde kkcde jkcde jjcde ijcde iicde hicde hhcde ghcde ggcde fgcde ffcde efcde eecde decde ddcde cdcde cccde bccde ...
result:
ok good solution
Test #20:
score: 0
Accepted
time: 600ms
memory: 4988kb
input:
4097
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde vwcde vvcde uvcde uucde tucde ttcde stcde sscde rscde rrcde qrcde qqcde pqcde ppcde opcde oocde nocde nncde mncde mmcde lmcde llcde klcde kkcde jkcde jjcde ijcde iicde hicde hhcde ghcde ggcde fgcde ffcde efcde eecde decde ddcde cdcde cccde bccde ...
result:
ok good solution
Test #21:
score: 0
Accepted
time: 610ms
memory: 5072kb
input:
4098
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde vwcde vvcde uvcde uucde tucde ttcde stcde sscde rscde rrcde qrcde qqcde pqcde ppcde opcde oocde nocde nncde mncde mmcde lmcde llcde klcde kkcde jkcde jjcde ijcde iicde hicde hhcde ghcde ggcde fgcde ffcde efcde eecde decde ddcde cdcde cccde bccde ...
result:
ok good solution
Test #22:
score: 0
Accepted
time: 563ms
memory: 4916kb
input:
3751
output:
abcde zbcde zzcde yzcde yycde xycde xxcde wxcde wwcde vwcde vvcde uvcde uucde tucde ttcde stcde sscde rscde rrcde qrcde qqcde pqcde ppcde opcde oocde nocde nncde mncde mmcde lmcde llcde klcde kkcde jkcde jjcde ijcde iicde hicde hhcde ghcde ggcde fgcde ffcde efcde eecde decde ddcde cdcde cccde bccde ...
result:
ok good solution