Submission #68173016


Source Code Expand

Copy
#include <stdio.h>
int N, M;
char S[1123456];
char T[1123456];
int main(void) {
int i;
int cnts[10] = {0};
int cur, last_ok = 0;
if (scanf("%d%d", &N, &M) != 2) return 1;
if (scanf("%1123455s", S) != 1) return 1;
if (scanf("%1123455s", T) != 1) return 1;
#if 0
if (N < 1 || 1000000 < N || M < 1 || 1000000 < M) return 42;
if (S[N] != '\0' || T[M] != '\0') return 42;
for (i = 0; i < N; i++) {
if (S[i] < '1' || '9' < S[i]) return 42;
}
for (i = 0; i < M; i++) {
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <stdio.h>

int N, M;
char S[1123456];
char T[1123456];

int main(void) {
	int i;
	int cnts[10] = {0};
	int cur, last_ok = 0;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	if (scanf("%1123455s", S) != 1) return 1;
	if (scanf("%1123455s", T) != 1) return 1;

#if 0
	if (N < 1 || 1000000 < N || M < 1 || 1000000 < M) return 42;
	if (S[N] != '\0' || T[M] != '\0') return 42;
	for (i = 0; i < N; i++) {
		if (S[i] < '1' || '9' < S[i]) return 42;
	}
	for (i = 0; i < M; i++) {
		if (T[i] < '1' || '9' < T[i]) return 42;
	}
#endif

	for (i = 0; i < M; i++) {
		int idx = T[i] - '0';
		if (0 <= idx && idx < 10) cnts[idx]++;
	}

	cur = 9;
	for (i = 0; i < N; i++) {
		while (cur >= 0 && cnts[cur] == 0) cur--;
		if (cur < 0) break;
		/* cur は、在庫がある最大の数字 */
		if (S[i] - '0' < cur) {
			/* 書き換えたほうが有利になる */
			S[i] = cur + '0';
			cnts[cur]--;
		}
		/* 最後の数字を消化できた? */
		last_ok = last_ok || S[i] == T[M - 1];
	}
	/* 最後の数字を消化できなかった */
	if (!last_ok) S[N - 1] = T[M - 1];

	puts(S);
	return 0;
}

/*

とにかく上位をつよくした方がつよい
最後の数字以外は捨てることができる (最後の数字を書くところに書けばいいので)

最後の数字以外の在庫をカウント
上位から見て、在庫がある数字で一番つよいやつを置く
ただし、それよりも既存の数字のほうがつよければスキップする
最後の数字と同じ数字を使おうとしたら、最後の数字を消化できる
最後まで最後の数字が残っていたら、それはクソザコなので、仕方ないから最下位に書いておく

*/

Submission Info

Submission Time
Task A - Replace Digits
User mikecat
Language C (gcc 12.2.0)
Score 400
Code Size 1762 Byte
Status AC
Exec Time 10 ms
Memory 3612 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 39
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_handmade_00.txt, 01_handmade_01.txt, 01_handmade_02.txt, 01_handmade_03.txt, 01_handmade_04.txt, 01_handmade_05.txt, 01_handmade_06.txt, 01_handmade_07.txt, 01_handmade_08.txt, 01_handmade_09.txt, 02_corner_00.txt, 02_corner_01.txt, 02_corner_02.txt, 02_corner_03.txt, 02_corner_04.txt, 02_corner_05.txt, 02_corner_06.txt, 02_corner_07.txt, 02_corner_08.txt, 03_random_00.txt, 03_random_01.txt, 03_random_02.txt, 03_random_03.txt, 03_random_04.txt, 03_random_05.txt, 03_random_06.txt, 03_random_07.txt, 03_random_08.txt, 03_random_09.txt, 03_random_10.txt, 04_max_00.txt, 04_max_01.txt, 04_max_02.txt, 04_max_03.txt, 04_max_04.txt, 04_max_05.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 0 ms 1624 KiB
00_sample_01.txt AC 0 ms 1588 KiB
00_sample_02.txt AC 0 ms 1616 KiB
01_handmade_00.txt AC 0 ms 1584 KiB
01_handmade_01.txt AC 0 ms 1612 KiB
01_handmade_02.txt AC 4 ms 2424 KiB
01_handmade_03.txt AC 4 ms 2492 KiB
01_handmade_04.txt AC 3 ms 2596 KiB
01_handmade_05.txt AC 8 ms 3552 KiB
01_handmade_06.txt AC 8 ms 3524 KiB
01_handmade_07.txt AC 8 ms 3400 KiB
01_handmade_08.txt AC 9 ms 3552 KiB
01_handmade_09.txt AC 8 ms 3472 KiB
02_corner_00.txt AC 3 ms 2208 KiB
02_corner_01.txt AC 4 ms 2452 KiB
02_corner_02.txt AC 4 ms 2312 KiB
02_corner_03.txt AC 2 ms 2088 KiB
02_corner_04.txt AC 7 ms 3392 KiB
02_corner_05.txt AC 3 ms 2340 KiB
02_corner_06.txt AC 6 ms 3184 KiB
02_corner_07.txt AC 4 ms 2484 KiB
02_corner_08.txt AC 3 ms 2140 KiB
03_random_00.txt AC 3 ms 2520 KiB
03_random_01.txt AC 1 ms 1684 KiB
03_random_02.txt AC 3 ms 2488 KiB
03_random_03.txt AC 2 ms 1904 KiB
03_random_04.txt AC 2 ms 2240 KiB
03_random_05.txt AC 3 ms 2204 KiB
03_random_06.txt AC 7 ms 2880 KiB
03_random_07.txt AC 6 ms 2636 KiB
03_random_08.txt AC 3 ms 2168 KiB
03_random_09.txt AC 2 ms 1688 KiB
03_random_10.txt AC 3 ms 2596 KiB
04_max_00.txt AC 10 ms 3556 KiB
04_max_01.txt AC 10 ms 3544 KiB
04_max_02.txt AC 10 ms 3612 KiB
04_max_03.txt AC 10 ms 3496 KiB
04_max_04.txt AC 10 ms 3396 KiB
04_max_05.txt AC 8 ms 3524 KiB


2025-08-03 (Sun)
04:11:10 +09:00