QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#554906#4237. Word LadderFortitude#AC ✓62ms10812kbC++231.3kb2024-09-09 17:30:012024-09-09 17:30:02

Judging History

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

  • [2024-09-09 17:30:02]
  • 评测
  • 测评结果:AC
  • 用时:62ms
  • 内存:10812kb
  • [2024-09-09 17:30:01]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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