Submission #68173016

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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

Judge Result