提出 #74530396 - AtCoder Grand Contest 077

コンテスト時間: 2026-03-29 21:00:00+0900 ~ 2026-03-30 00:00:00+0900 (180分) AtCoderホームへ戻る

提出 #74530396

ソースコード拡げる

#include<cstdio>
int n;
char a[500100];
char b[500100];
char s[500100];
int locs[500100][2];
int ansl;
int ans[500100][2];
void putans(int pa, int pb) {
	if (pa < pb) {
		ans[ansl][0] = pa;
		ans[ansl][1] = pb;
	}
	else {
		ans[ansl][0] = pb;
		ans[ansl][1] = pa;
	}
	ansl++;
}
void solve(int l, int r) {
	int acnt, bcnt;
	acnt = 0;
	bcnt = 0;
	for (int i = l + 1; i < r; i++) {
		if (a[i] == 'A')acnt++;
		if (a[i] == 'B')bcnt++;
	}
	if (acnt < bcnt) {
		int ccnt = 0;
		int dcnt = 0;
		for (int i = l + 1; i < r; i++) {
			if (a[i] == 'A') {
				locs[ccnt][0] = i;
				ccnt++;
			}
			if (b[l + r - i] == 'A') {
				locs[dcnt][1] = i;
				dcnt++;
			}
		}
		for (int i = ccnt - 1; i >= 0; i--) {
			if (locs[i][0] < locs[i][1]) {
				putans(locs[i][0], locs[i][1]);
				char t = a[locs[i][0]];
				a[locs[i][0]] = a[locs[i][1]];
				a[locs[i][1]] = t;
			}
		}
	}
	else {
		int ccnt = 0;
		int dcnt = 0;
		for (int i = l + 1; i < r; i++) {
			if (a[i] == 'B') {
				locs[ccnt][0] = i;
				ccnt++;
			}
			if (b[l + r - i] == 'B') {
				locs[dcnt][1] = i;
				dcnt++;
			}
		}
		for (int i = 0; i < ccnt; i++) {
			if (locs[i][0] > locs[i][1]) {
				putans(locs[i][0], locs[i][1]);
				char t = a[locs[i][0]];
				a[locs[i][0]] = a[locs[i][1]];
				a[locs[i][1]] = t;
			}
		}
	}
	putans(l, r);
	for (int i = l; i <= r; i++) {
		s[i] = a[i];
	}
	for (int i = l; i <= r; i++) {
		a[i] = s[l + r - i];
	}
	if (acnt < bcnt) {
		int ccnt = 0;
		int dcnt = 0;
		for (int i = l + 1; i < r; i++) {
			if (a[i] == 'A') {
				locs[ccnt][0] = i;
				ccnt++;
			}
			if (b[i] == 'A') {
				locs[dcnt][1] = i;
				dcnt++;
			}
		}
		for (int i = ccnt - 1; i >= 0; i--) {
			if (locs[i][0] < locs[i][1]) {
				putans(locs[i][0], locs[i][1]);
				char t = a[locs[i][0]];
				a[locs[i][0]] = a[locs[i][1]];
				a[locs[i][1]] = t;
			}
		}
	}
	else {
		int ccnt = 0;
		int dcnt = 0;
		for (int i = l + 1; i < r; i++) {
			if (a[i] == 'B') {
				locs[ccnt][0] = i;
				ccnt++;
			}
			if (b[i] == 'B') {
				locs[dcnt][1] = i;
				dcnt++;
			}
		}
		for (int i = 0; i < ccnt; i++) {
			if (locs[i][0] > locs[i][1]) {
				putans(locs[i][0], locs[i][1]);
				char t = a[locs[i][0]];
				a[locs[i][0]] = a[locs[i][1]];
				a[locs[i][1]] = t;
			}
		}
	}
}
int main() {
	int tcn;
	scanf("%d", &tcn);
	while (tcn--) {
		scanf("%d", &n);
		scanf("%s", a);
		scanf("%s", b);
		int mindiff = n;
		for (int i = 0; i < n; i++) {
			if (a[i] != b[i]) {
				mindiff = i;
				break;
			}
		}
		int maxdiff = -1;
		for (int i = n - 1; i >= 0; i--) {
			if (a[i] != b[i]) {
				maxdiff = i;
				break;
			}
		}
		if (mindiff == n) {
			printf("Yes\n");
			printf("0\n");
			continue;
		}
		if (a[mindiff] == 'B' || a[maxdiff] == 'A') {
			printf("No\n");
			continue;
		}
		int acnt, bcnt;
		acnt = 0;
		bcnt = 0;
		for (int i = 0; i < n; i++) {
			if (a[i] == 'A')acnt++;
			if (a[i] == 'B')bcnt++;
		}
		int gacnt, gbcnt;
		gacnt = 0;
		gbcnt = 0;
		for (int i = 0; i < n; i++) {
			if (b[i] == 'A')gacnt++;
			if (b[i] == 'B')gbcnt++;
		}
		if (gacnt != acnt) {
			printf("No\n");
			continue;
		}
		ansl = 0;
		solve(mindiff, maxdiff);
		printf("Yes\n");
		printf("%d\n", ansl);
		for (int i = 0; i < ansl; i++) {
			printf("%d %d\n", ans[i][0] + 1, ans[i][1] + 1);
		}
	}
	return 0;
}

提出情報

提出日時	2026-03-29 21:44:06+0900
問題	A - Reverse A…B
ユーザ	gs12117
言語	C++23 (GCC 15.2.0)
得点	800
コード長	3440 Byte
結果	AC
実行時間	28 ms
メモリ	8960 KiB

ジャッジ結果

セット名

Sample

All

得点 / 配点

0 / 0

800 / 800

結果

× 1

× 84

セット名	テストケース
Sample	00_sample_00.txt
All	00_sample_00.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 02_small_00.txt, 02_small_01.txt, 02_small_02.txt, 02_small_03.txt, 02_small_04.txt, 02_small_05.txt, 02_small_06.txt, 02_small_07.txt, 02_small_08.txt, 02_small_09.txt, 02_small_10.txt, 02_small_11.txt, 02_small_12.txt, 03_large_00.txt, 04_hack_00.txt, 04_hack_01.txt, 04_hack_02.txt, 04_hack_03.txt, 04_hack_04.txt, 04_hack_05.txt, 04_hack_06.txt, 04_hack_07.txt, 04_hack_08.txt, 04_hack_09.txt, 04_hack_10.txt, 04_hack_11.txt, 04_hack_12.txt, 04_hack_13.txt, 04_hack_14.txt, 04_hack_15.txt, 04_hack_16.txt, 04_hack_17.txt, 04_hack_18.txt, 04_hack_19.txt, 04_hack_20.txt, 04_hack_21.txt, 04_hack_22.txt, 04_hack_23.txt, 04_hack_24.txt, 04_hack_25.txt, 04_hack_26.txt, 04_hack_27.txt, 04_hack_28.txt, 04_hack_29.txt, 04_hack_30.txt, 04_hack_31.txt, 04_hack_32.txt, 04_hack_33.txt, 04_hack_34.txt, 04_hack_35.txt, 04_hack_36.txt, 04_hack_37.txt, 04_hack_38.txt

ケース名	結果	実行時間	メモリ
00_sample_00.txt	AC	1 ms	1636 KiB
01_random_00.txt	AC	14 ms	3968 KiB
01_random_01.txt	AC	13 ms	4184 KiB
01_random_02.txt	AC	8 ms	2876 KiB
01_random_03.txt	AC	3 ms	2324 KiB
01_random_04.txt	AC	6 ms	2864 KiB
01_random_05.txt	AC	6 ms	2824 KiB
01_random_06.txt	AC	15 ms	4588 KiB
01_random_07.txt	AC	2 ms	2224 KiB
01_random_08.txt	AC	2 ms	2304 KiB
01_random_09.txt	AC	2 ms	2156 KiB
01_random_10.txt	AC	4 ms	2512 KiB
01_random_11.txt	AC	9 ms	3196 KiB
01_random_12.txt	AC	2 ms	2700 KiB
01_random_13.txt	AC	10 ms	3552 KiB
01_random_14.txt	AC	2 ms	2608 KiB
01_random_15.txt	AC	3 ms	2072 KiB
01_random_16.txt	AC	2 ms	2028 KiB
01_random_17.txt	AC	2 ms	2184 KiB
01_random_18.txt	AC	3 ms	2368 KiB
01_random_19.txt	AC	2 ms	2404 KiB
01_random_20.txt	AC	2 ms	2528 KiB
01_random_21.txt	AC	10 ms	4096 KiB
01_random_22.txt	AC	2 ms	2620 KiB
01_random_23.txt	AC	2 ms	2556 KiB
01_random_24.txt	AC	2 ms	2556 KiB
01_random_25.txt	AC	2 ms	2696 KiB
01_random_26.txt	AC	2 ms	2624 KiB
01_random_27.txt	AC	26 ms	7920 KiB
01_random_28.txt	AC	28 ms	8252 KiB
01_random_29.txt	AC	3 ms	2696 KiB
02_small_00.txt	AC	16 ms	1544 KiB
02_small_01.txt	AC	16 ms	1556 KiB
02_small_02.txt	AC	16 ms	1548 KiB
02_small_03.txt	AC	16 ms	1672 KiB
02_small_04.txt	AC	14 ms	1600 KiB
02_small_05.txt	AC	7 ms	1840 KiB
02_small_06.txt	AC	7 ms	1532 KiB
02_small_07.txt	AC	7 ms	1604 KiB
02_small_08.txt	AC	7 ms	1508 KiB
02_small_09.txt	AC	7 ms	1672 KiB
02_small_10.txt	AC	7 ms	1540 KiB
02_small_11.txt	AC	7 ms	1712 KiB
02_small_12.txt	AC	1 ms	1624 KiB
03_large_00.txt	AC	4 ms	5168 KiB
04_hack_00.txt	AC	24 ms	8960 KiB
04_hack_01.txt	AC	24 ms	8776 KiB
04_hack_02.txt	AC	23 ms	6844 KiB
04_hack_03.txt	AC	24 ms	8960 KiB
04_hack_04.txt	AC	23 ms	5692 KiB
04_hack_05.txt	AC	23 ms	7876 KiB
04_hack_06.txt	AC	3 ms	2284 KiB
04_hack_07.txt	AC	20 ms	5080 KiB
04_hack_08.txt	AC	6 ms	2532 KiB
04_hack_09.txt	AC	8 ms	3168 KiB
04_hack_10.txt	AC	7 ms	3040 KiB
04_hack_11.txt	AC	3 ms	2240 KiB
04_hack_12.txt	AC	2 ms	2540 KiB
04_hack_13.txt	AC	11 ms	3672 KiB
04_hack_14.txt	AC	4 ms	2480 KiB
04_hack_15.txt	AC	9 ms	2400 KiB
04_hack_16.txt	AC	2 ms	2016 KiB
04_hack_17.txt	AC	2 ms	2280 KiB
04_hack_18.txt	AC	2 ms	2324 KiB
04_hack_19.txt	AC	3 ms	2824 KiB
04_hack_20.txt	AC	18 ms	5588 KiB
04_hack_21.txt	AC	6 ms	3208 KiB
04_hack_22.txt	AC	2 ms	2480 KiB
04_hack_23.txt	AC	13 ms	4708 KiB
04_hack_24.txt	AC	12 ms	4092 KiB
04_hack_25.txt	AC	9 ms	2696 KiB
04_hack_26.txt	AC	6 ms	3452 KiB
04_hack_27.txt	AC	17 ms	5516 KiB
04_hack_28.txt	AC	10 ms	3784 KiB
04_hack_29.txt	AC	9 ms	3348 KiB
04_hack_30.txt	AC	19 ms	6804 KiB
04_hack_31.txt	AC	23 ms	7512 KiB
04_hack_32.txt	AC	20 ms	3960 KiB
04_hack_33.txt	AC	16 ms	2912 KiB
04_hack_34.txt	AC	3 ms	2152 KiB
04_hack_35.txt	AC	3 ms	2688 KiB
04_hack_36.txt	AC	6 ms	2684 KiB
04_hack_37.txt	AC	8 ms	3208 KiB
04_hack_38.txt	AC	3 ms	2656 KiB