QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#375606 | #4237. Word Ladder | 8BQube# | AC ✓ | 167ms | 5440kb | C++20 | 1.5kb | 2024-04-03 14:06:58 | 2024-04-03 14:06:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())
vector<string> gen(vector<string> s) {
vector<string> vec, res;
for (char i = 'a'; i <= 'z'; ++i) {
vec.pb(string(2, i));
if (i < 'z')
vec.pb(string(2, i)), vec.back()[1] += 1;
}
for (int i = 0; i < SZ(vec); ++i) {
if (i % 2 == 0) {
for (auto ss : s)
res.pb(vec[i] + ss);
}
else if (i % 2 == 1) {
res.pb(vec[i] + s.back());
reverse(ALL(s));
}
}
return res;
}
bool has_edge(string a, string b) {
int diff = 0;
for (int i = 0; i < SZ(a); ++i)
if (a[i] != b[i])
++diff;
return diff == 1;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
vector<string> vec;
for (char i = 'a'; i <= 'z'; ++i) {
vec.pb(string(2, i));
if (i < 'z')
vec.pb(string(2, i)), vec.back()[1] += 1;
}
while (SZ(vec) < n) {
vec = gen(vec);
}
for (int i = 0; i < n; ++i)
cout << vec[i] << "\n";
for (int i = 0; i + 1 < n; ++i) {
assert(has_edge(vec[i], vec[i + 1]));
for (int j = i + 2; j < n; ++j)
assert(!has_edge(vec[i], vec[j]));
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
input:
5
output:
aa ab bb bc cc
result:
ok good solution
Test #2:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
3
output:
aa ab bb
result:
ok good solution
Test #3:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
4
output:
aa ab bb bc
result:
ok good solution
Test #4:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
6
output:
aa ab bb bc cc cd
result:
ok good solution
Test #5:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
7
output:
aa ab bb bc cc cd dd
result:
ok good solution
Test #6:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
8
output:
aa ab bb bc cc cd dd de
result:
ok good solution
Test #7:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
9
output:
aa ab bb bc cc cd dd de ee
result:
ok good solution
Test #8:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
10
output:
aa ab bb bc cc cd dd de ee ef
result:
ok good solution
Test #9:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
64
output:
aaaa aaab aabb aabc aacc aacd aadd aade aaee aaef aaff aafg aagg aagh aahh aahi aaii aaij aajj aajk aakk aakl aall aalm aamm aamn aann aano aaoo aaop aapp aapq aaqq aaqr aarr aars aass aast aatt aatu aauu aauv aavv aavw aaww aawx aaxx aaxy aayy aayz aazz abzz bbzz bbyz bbyy bbxy bbxx bbwx bbww bbvw ...
result:
ok good solution
Test #10:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
51
output:
aa ab bb bc cc cd dd de ee ef ff fg gg gh hh hi ii ij jj jk kk kl ll lm mm mn nn no oo op pp pq qq qr rr rs ss st tt tu uu uv vv vw ww wx xx xy yy yz zz
result:
ok good solution
Test #11:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
97
output:
aaaa aaab aabb aabc aacc aacd aadd aade aaee aaef aaff aafg aagg aagh aahh aahi aaii aaij aajj aajk aakk aakl aall aalm aamm aamn aann aano aaoo aaop aapp aapq aaqq aaqr aarr aars aass aast aatt aatu aauu aauv aavv aavw aaww aawx aaxx aaxy aayy aayz aazz abzz bbzz bbyz bbyy bbxy bbxx bbwx bbww bbvw ...
result:
ok good solution
Test #12:
score: 0
Accepted
time: 1ms
memory: 3740kb
input:
100
output:
aaaa aaab aabb aabc aacc aacd aadd aade aaee aaef aaff aafg aagg aagh aahh aahi aaii aaij aajj aajk aakk aakl aall aalm aamm aamn aann aano aaoo aaop aapp aapq aaqq aaqr aarr aars aass aast aatt aatu aauu aauv aavv aavw aaww aawx aaxx aaxy aayy aayz aazz abzz bbzz bbyz bbyy bbxy bbxx bbwx bbww bbvw ...
result:
ok good solution
Test #13:
score: 0
Accepted
time: 7ms
memory: 3740kb
input:
1000
output:
aaaa aaab aabb aabc aacc aacd aadd aade aaee aaef aaff aafg aagg aagh aahh aahi aaii aaij aajj aajk aakk aakl aall aalm aamm aamn aann aano aaoo aaop aapp aapq aaqq aaqr aarr aars aass aast aatt aatu aauu aauv aavv aavw aaww aawx aaxx aaxy aayy aayz aazz abzz bbzz bbyz bbyy bbxy bbxx bbwx bbww bbvw ...
result:
ok good solution
Test #14:
score: 0
Accepted
time: 6ms
memory: 3672kb
input:
1001
output:
aaaa aaab aabb aabc aacc aacd aadd aade aaee aaef aaff aafg aagg aagh aahh aahi aaii aaij aajj aajk aakk aakl aall aalm aamm aamn aann aano aaoo aaop aapp aapq aaqq aaqr aarr aars aass aast aatt aatu aauu aauv aavv aavw aaww aawx aaxx aaxy aayy aayz aazz abzz bbzz bbyz bbyy bbxy bbxx bbwx bbww bbvw ...
result:
ok good solution
Test #15:
score: 0
Accepted
time: 7ms
memory: 3952kb
input:
1024
output:
aaaa aaab aabb aabc aacc aacd aadd aade aaee aaef aaff aafg aagg aagh aahh aahi aaii aaij aajj aajk aakk aakl aall aalm aamm aamn aann aano aaoo aaop aapp aapq aaqq aaqr aarr aars aass aast aatt aatu aauu aauv aavv aavw aaww aawx aaxx aaxy aayy aayz aazz abzz bbzz bbyz bbyy bbxy bbxx bbwx bbww bbvw ...
result:
ok good solution
Test #16:
score: 0
Accepted
time: 7ms
memory: 3720kb
input:
1025
output:
aaaa aaab aabb aabc aacc aacd aadd aade aaee aaef aaff aafg aagg aagh aahh aahi aaii aaij aajj aajk aakk aakl aall aalm aamm aamn aann aano aaoo aaop aapp aapq aaqq aaqr aarr aars aass aast aatt aatu aauu aauv aavv aavw aaww aawx aaxx aaxy aayy aayz aazz abzz bbzz bbyz bbyy bbxy bbxx bbwx bbww bbvw ...
result:
ok good solution
Test #17:
score: 0
Accepted
time: 167ms
memory: 5440kb
input:
5000
output:
aaaaaa aaaaab aaaabb aaaabc aaaacc aaaacd aaaadd aaaade aaaaee aaaaef aaaaff aaaafg aaaagg aaaagh aaaahh aaaahi aaaaii aaaaij aaaajj aaaajk aaaakk aaaakl aaaall aaaalm aaaamm aaaamn aaaann aaaano aaaaoo aaaaop aaaapp aaaapq aaaaqq aaaaqr aaaarr aaaars aaaass aaaast aaaatt aaaatu aaaauu aaaauv aaaavv...
result:
ok good solution
Test #18:
score: 0
Accepted
time: 158ms
memory: 5284kb
input:
4999
output:
aaaaaa aaaaab aaaabb aaaabc aaaacc aaaacd aaaadd aaaade aaaaee aaaaef aaaaff aaaafg aaaagg aaaagh aaaahh aaaahi aaaaii aaaaij aaaajj aaaajk aaaakk aaaakl aaaall aaaalm aaaamm aaaamn aaaann aaaano aaaaoo aaaaop aaaapp aaaapq aaaaqq aaaaqr aaaarr aaaars aaaass aaaast aaaatt aaaatu aaaauu aaaauv aaaavv...
result:
ok good solution
Test #19:
score: 0
Accepted
time: 105ms
memory: 5328kb
input:
4096
output:
aaaaaa aaaaab aaaabb aaaabc aaaacc aaaacd aaaadd aaaade aaaaee aaaaef aaaaff aaaafg aaaagg aaaagh aaaahh aaaahi aaaaii aaaaij aaaajj aaaajk aaaakk aaaakl aaaall aaaalm aaaamm aaaamn aaaann aaaano aaaaoo aaaaop aaaapp aaaapq aaaaqq aaaaqr aaaarr aaaars aaaass aaaast aaaatt aaaatu aaaauu aaaauv aaaavv...
result:
ok good solution
Test #20:
score: 0
Accepted
time: 109ms
memory: 5320kb
input:
4097
output:
aaaaaa aaaaab aaaabb aaaabc aaaacc aaaacd aaaadd aaaade aaaaee aaaaef aaaaff aaaafg aaaagg aaaagh aaaahh aaaahi aaaaii aaaaij aaaajj aaaajk aaaakk aaaakl aaaall aaaalm aaaamm aaaamn aaaann aaaano aaaaoo aaaaop aaaapp aaaapq aaaaqq aaaaqr aaaarr aaaars aaaass aaaast aaaatt aaaatu aaaauu aaaauv aaaavv...
result:
ok good solution
Test #21:
score: 0
Accepted
time: 106ms
memory: 5324kb
input:
4098
output:
aaaaaa aaaaab aaaabb aaaabc aaaacc aaaacd aaaadd aaaade aaaaee aaaaef aaaaff aaaafg aaaagg aaaagh aaaahh aaaahi aaaaii aaaaij aaaajj aaaajk aaaakk aaaakl aaaall aaaalm aaaamm aaaamn aaaann aaaano aaaaoo aaaaop aaaapp aaaapq aaaaqq aaaaqr aaaarr aaaars aaaass aaaast aaaatt aaaatu aaaauu aaaauv aaaavv...
result:
ok good solution
Test #22:
score: 0
Accepted
time: 87ms
memory: 5340kb
input:
3751
output:
aaaaaa aaaaab aaaabb aaaabc aaaacc aaaacd aaaadd aaaade aaaaee aaaaef aaaaff aaaafg aaaagg aaaagh aaaahh aaaahi aaaaii aaaaij aaaajj aaaajk aaaakk aaaakl aaaall aaaalm aaaamm aaaamn aaaann aaaano aaaaoo aaaaop aaaapp aaaapq aaaaqq aaaaqr aaaarr aaaars aaaass aaaast aaaatt aaaatu aaaauu aaaauv aaaavv...
result:
ok good solution