Submission #65151789

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, K;
char S[212345];
char S_left_max[212345], S_right_max[212345];
int left_min_cnt[212345], left_max_cnt[212345];
int right_min_cnt[212345], right_max_cnt[212345];
int main(void) {
  int i;
  if (scanf("%d%d", &N, &K) != 2) return 1;
  if (scanf("%212344s", S) != 1) return 1;
  for (i = 0; i < N; i++) {
    if (S[i] == '?') {
      S_left_max[i] = ".o"[(i == 0 || S_left_max[i - 1] != 'o') && S[i + 1] != 'o'];
    } else {
      S_left_max[i] = S[i];
    }
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

int N, K;
char S[212345];

char S_left_max[212345], S_right_max[212345];

int left_min_cnt[212345], left_max_cnt[212345];
int right_min_cnt[212345], right_max_cnt[212345];

int main(void) {
	int i;
	if (scanf("%d%d", &N, &K) != 2) return 1;
	if (scanf("%212344s", S) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (S[i] == '?') {
			S_left_max[i] = ".o"[(i == 0 || S_left_max[i - 1] != 'o') && S[i + 1] != 'o'];
		} else {
			S_left_max[i] = S[i];
		}
	}
	for (i = N - 1; i >= 0; i--) {
		if (S[i] == '?') {
			S_right_max[i] = ".o"[S_right_max[i + 1] != 'o' && (i == 0 || S[i - 1] != 'o')];
		} else {
			S_right_max[i] = S[i];
		}
	}
	left_min_cnt[0] = S[0] == 'o';
	left_max_cnt[0] = S_left_max[0] == 'o';
	for (i =  1; i < N; i++) {
		left_min_cnt[i] = left_min_cnt[i - 1] + (S[i] == 'o');
		left_max_cnt[i] = left_max_cnt[i - 1] + (S_left_max[i] == 'o');
	}
	for (i = N - 1; i >= 0; i--) {
		right_min_cnt[i] = right_min_cnt[i + 1] + (S[i] == 'o');
		right_max_cnt[i] = right_max_cnt[i + 1] + (S_right_max[i] == 'o');
	}
	for (i = 0; i < N; i++) {
		if (S[i] == '?') {
			int yes = 0;
			/* . にして条件を満たせるか */
			if (
				(i == 0 ? 0 : left_min_cnt[i - 1]) + right_min_cnt[i + 1] <= K &&
				(i == 0 ? 0 : left_max_cnt[i - 1]) + right_max_cnt[i + 1] >= K
			) {
				yes |= 1;
			}
			/* o にして条件を満たせるか */
			if (
				(i == 0 || S[i - 1] != 'o') &&
				S[i + 1] != 'o' &&
				(i <= 1 ? 0 : left_min_cnt[i - 2]) + 1 + right_min_cnt[i + 2] <= K &&
				(i <= 1 ? 0 : left_max_cnt[i - 2]) + 1 + right_max_cnt[i + 2] >= K
			) {
				yes |= 2;
			}
			/* 結果を出力する */
			putchar("!.o?"[yes]);
		} else {
			putchar(S[i]);
		}
	}
	putchar('\n');
	return 0;
}

Submission Info

Judge Result