結果

問題 No.930 数列圧縮
コンテスト
ユーザー bal4u
提出日時 2019-12-09 07:27:42
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 9 ms / 2,000 ms
コード長 1,698 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 31,744 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-11 18:35:48
合計ジャッジ時間 1,890 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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 N, M;
int ans[100005], w;

int rec() {
	int i, j, mi, ma, f = 0;

    mi = t[1].a, ma = t[N].a;
    while (w < M) {
        i = t[N].pre;
        if (t[i].a > ma) break;
        ans[w++] = t[i].a, f = 1;
        t[t[i].pre].nxt = N;
        t[N].pre = t[i].pre;
    }
    while (w < M) {
        i = t[1].nxt;
        if (mi > t[i].a) break;
        ans[w++] = t[i].a, f = 1;
        t[t[i].nxt].pre = 1;
        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 (t[i].a < mi || j == N) {
				ans[w++] = t[i].a, f = 1;
				t[t[i].pre].nxt = j;
				t[j].pre = t[i].pre;
			} else { // if (t[j].a > ma) {
				ans[w++] = t[j].a, f = 1;
				t[t[j].nxt].pre = i;
				t[i].nxt = t[j].nxt;
				i = t[i].pre;
			}
		}
	}
	return f;
}
		
int main()
{
	int i;
	
	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;
	while (rec());
	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