結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0