Submission #77254903

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
struct meow {
  char c;
  int cnt;
};
int cmp(const void* x, const void* y) {
  struct meow a = *(const struct meow*)x, b = *(const struct meow*)y;
  return
    ((a.cnt < b.cnt) - (a.cnt > b.cnt)) * 2 +
    ((a.c > b.c) - (a.c < b.c));
}
int main(void) {
  int T, tc;
  char buf[32];
  if (fgets(buf, sizeof(buf), stdin) == NULL || sscanf(buf, "%d", &T) != 1) return 1;
  for (tc = 0; tc < T; tc++) {
    struct meow cnt[26];
    int c;
    int i;
    int cnt_all;
    for (i = 0; i < 26; i++) cnt[i] = (struct meow){ 'a' + i, 0 };
    while ((c = getchar()) != '\n' && c != EOF) {
      int id = c - 'a';
      if (0 <= id && id < 26) cnt[id].cnt++;
    }
    qsort(cnt, 26, sizeof(*cnt), cmp);
    for (i = 0, cnt_all = 0; i < 26; i++) cnt_all += cnt[i].cnt;
    if (cnt[0].cnt > (cnt_all + 1) / 2) {
      puts("No");
    } else {
      char* res = malloc(cnt_all + 1);
      int p;
      if (res == NULL) return 2;
      puts("Yes");
      for (i = 0, p = 0; i < 26; i++) {
        int j;
        for (j = 0; j < cnt[i].cnt; j++) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

struct meow {
	char c;
	int cnt;
};

int cmp(const void* x, const void* y) {
	struct meow a = *(const struct meow*)x, b = *(const struct meow*)y;
	return
		((a.cnt < b.cnt) - (a.cnt > b.cnt)) * 2 +
		((a.c > b.c) - (a.c < b.c));
}

int main(void) {
	int T, tc;
	char buf[32];
	if (fgets(buf, sizeof(buf), stdin) == NULL || sscanf(buf, "%d", &T) != 1) return 1;
	for (tc = 0; tc < T; tc++) {
		struct meow cnt[26];
		int c;
		int i;
		int cnt_all;
		for (i = 0; i < 26; i++) cnt[i] = (struct meow){ 'a' + i, 0 };
		while ((c = getchar()) != '\n' && c != EOF) {
			int id = c - 'a';
			if (0 <= id && id < 26) cnt[id].cnt++;
		}
		qsort(cnt, 26, sizeof(*cnt), cmp);
		for (i = 0, cnt_all = 0; i < 26; i++) cnt_all += cnt[i].cnt;
		if (cnt[0].cnt > (cnt_all + 1) / 2) {
			puts("No");
		} else {
			char* res = malloc(cnt_all + 1);
			int p;
			if (res == NULL) return 2;
			puts("Yes");
			for (i = 0, p = 0; i < 26; i++) {
				int j;
				for (j = 0; j < cnt[i].cnt; j++) {
					res[p] = cnt[i].c;
					p += 2;
					if (p >= cnt_all) p = 1;
				}
			}
			res[cnt_all] = '\0';
			puts(res);
			free(res);
		}
	}
	return 0;
}

/*

oxoxoxoxo

oxoxoxoxox

ある文字が全体の半分 (切り上げ) を超える → No
otherwise → Yes (多い順に一つおきに流し込む)

*/

Submission Info

Judge Result