QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#554906 | #4237. Word Ladder | Fortitude# | AC ✓ | 62ms | 10812kb | C++23 | 1.3kb | 2024-09-09 17:30:01 | 2024-09-09 17:30:02 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)X.size()
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
using ll = long long;
using pii = pair <int, int>;
const int N = 2e5 + 5;
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
string cur = "aaaa";
map <string, int> was, wass[4];
for (int k = 0; k < 4; ++k) {
string t = cur.substr(0, k) + cur.substr(k, 4 - k - 1);
if (wass[k].count(t) == 0)
wass[k][t] = 0;
}
for (int i = 0; i < n; ++i) {
cout << cur << '\n';
string ok = cur;
was[cur] = 1;
string nxt = "-1";
for (int j = 0; j < 4; ++j) {
char x = cur[j];
for (char c = 'a'; c <= 'z'; ++c) {
if (c == x)
continue;
cur[j] = c;
if (was[cur])
continue;
bool bad = 0;
for (int k = 0; k < 4; ++k) {
string t = cur.substr(0, k) + cur.substr(k + 1, 4 - k - 1);
if (wass[k].count(t) && wass[k][t] < i) {
bad = 1;
break;
}
}
if (!bad) {
nxt = cur;
break;
}
}
if (nxt != "-1")
break;
cur[j] = x;
}
assert(nxt != "-1");
cur = nxt;
for (int k = 0; k < 4; ++k) {
string t = cur.substr(0, k) + cur.substr(k + 1, 4 - k - 1);
if (!wass[k].count(t)) {
wass[k][t] = i + 1;
}
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3568kb
input:
5
output:
aaaa baaa bbaa cbaa ccaa
result:
ok good solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
3
output:
aaaa baaa bbaa
result:
ok good solution
Test #3:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
4
output:
aaaa baaa bbaa cbaa
result:
ok good solution
Test #4:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
6
output:
aaaa baaa bbaa cbaa ccaa dcaa
result:
ok good solution
Test #5:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
7
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa
result:
ok good solution
Test #6:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
8
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa
result:
ok good solution
Test #7:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
9
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa
result:
ok good solution
Test #8:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
10
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa
result:
ok good solution
Test #9:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
64
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba daba caba cdba bdba bcba ...
result:
ok good solution
Test #10:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
51
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa
result:
ok good solution
Test #11:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
97
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba daba caba cdba bdba bcba ...
result:
ok good solution
Test #12:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
100
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba daba caba cdba bdba bcba ...
result:
ok good solution
Test #13:
score: 0
Accepted
time: 6ms
memory: 5192kb
input:
1000
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba daba caba cdba bdba bcba ...
result:
ok good solution
Test #14:
score: 0
Accepted
time: 9ms
memory: 4924kb
input:
1001
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba daba caba cdba bdba bcba ...
result:
ok good solution
Test #15:
score: 0
Accepted
time: 10ms
memory: 4892kb
input:
1024
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba daba caba cdba bdba bcba ...
result:
ok good solution
Test #16:
score: 0
Accepted
time: 10ms
memory: 4980kb
input:
1025
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba daba caba cdba bdba bcba ...
result:
ok good solution
Test #17:
score: 0
Accepted
time: 62ms
memory: 10812kb
input:
5000
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba daba caba cdba bdba bcba ...
result:
ok good solution
Test #18:
score: 0
Accepted
time: 62ms
memory: 10648kb
input:
4999
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba daba caba cdba bdba bcba ...
result:
ok good solution
Test #19:
score: 0
Accepted
time: 49ms
memory: 9228kb
input:
4096
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba daba caba cdba bdba bcba ...
result:
ok good solution
Test #20:
score: 0
Accepted
time: 49ms
memory: 9580kb
input:
4097
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba daba caba cdba bdba bcba ...
result:
ok good solution
Test #21:
score: 0
Accepted
time: 45ms
memory: 9296kb
input:
4098
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba daba caba cdba bdba bcba ...
result:
ok good solution
Test #22:
score: 0
Accepted
time: 44ms
memory: 8836kb
input:
3751
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba daba caba cdba bdba bcba ...
result:
ok good solution