結果

問題 No.930 数列圧縮
ユーザー bal4ubal4u
提出日時 2019-12-09 08:32:47
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 1,675 bytes
コンパイル時間 481 ms
コンパイル使用メモリ 31,872 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-11 19:57:37
合計ジャッジ時間 2,161 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 5 ms
5,376 KB
testcase_09 AC 7 ms
5,376 KB
testcase_10 AC 6 ms
5,376 KB
testcase_11 AC 5 ms
5,376 KB
testcase_12 AC 7 ms
5,376 KB
testcase_13 AC 4 ms
5,376 KB
testcase_14 AC 4 ms
5,376 KB
testcase_15 AC 7 ms
5,376 KB
testcase_16 AC 7 ms
5,376 KB
testcase_17 AC 8 ms
5,376 KB
testcase_18 AC 8 ms
5,376 KB
testcase_19 AC 8 ms
5,376 KB
testcase_20 AC 8 ms
5,376 KB
testcase_21 AC 7 ms
5,376 KB
testcase_22 AC 1 ms
5,376 KB
testcase_23 AC 6 ms
5,376 KB
testcase_24 AC 0 ms
5,376 KB
testcase_25 AC 1 ms
5,376 KB
testcase_26 AC 0 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// yuki 930 数列圧縮
// 2019.12.8 bal4u

#include <stdio.h>

int getchar_unlocked(void);
int putchar_unlocked(int c);
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

void out(int n) { // 非負整数の表示（出力）
	int i = 0; char b[30];
	while (n) b[i++] = n % 10 + '0', n /= 10;
	while (i--) pc(b[i]);
}

void outs(char *s) { while (*s) pc(*s++); pc('\n'); }

typedef struct { int pre, nxt, a; } T;
T t[100005];
int ans[100005], w;

int main()
{
	int i, j, mi, ma, N, M;
	
	N = in(), M = N-1;
    for (i = 1; i <= N; ++i) {
        t[i].pre = i-1, t[i].nxt = i+1, t[i].a = in();
    }
	t[N].nxt = 0;
    mi = t[1].a, ma = t[N].a;

	while (w < M) {
		int f = 0;

		i = t[N].pre; while (w < M) {
	        if (t[i].a > ma) break;
	        ans[w++] = t[i].a, f = 1;
	        t[t[i].pre].nxt = N;
	        i = t[N].pre = t[i].pre;
	    }
		i = t[1].nxt; while (w < M) {
	        if (mi > t[i].a) break;
	        ans[w++] = t[i].a, f = 1;
	        t[t[i].nxt].pre = 1;
	        i = t[1].nxt = t[i].nxt;
	    }
		i = 1; while (w < M) {
			i = t[i].nxt, j = t[i].nxt;
			if (j == 0) break;
			if (t[i].a < t[j].a) {
				if (j == N || t[i].a < mi) {
					ans[w++] = t[i].a, f = 1;
					t[t[i].pre].nxt = j;
					t[j].pre = t[i].pre;
				} else {
					ans[w++] = t[j].a, f = 1;
					t[t[j].nxt].pre = i;
					t[i].nxt = t[j].nxt;
					i = t[i].pre;
				}
			}
		}
		if (!f) break;
	}
	if (w < M) outs("No");
	else {
		outs("Yes");
		out(ans[0]);
		for (i = 1; i < w; i++) pc(' '), out(ans[i]);
		pc('\n');
	}
   	return 0;
}
0