結果
問題 | No.1834 1D Gravity |
ユーザー |
👑 |
提出日時 | 2022-01-16 12:06:30 |
言語 | C (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,832 bytes |
コンパイル時間 | 1,283 ms |
コンパイル使用メモリ | 31,616 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-23 09:36:26 |
合計ジャッジ時間 | 3,766 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 WA * 1 |
ソースコード
#include <stdio.h>void chmax(int* a, int b){if (*a < b) *a = b;}int naive(int N, int m[], int K){int i, j, k, len, num, tmp[2][200003] = {}, cur, prev;for (i = 1; i <= N; i++) tmp[0][i] = m[i];for (k = 1, cur = 1, prev = 0; k <= K; k++, cur ^= 1, prev ^= 1) {for (i = 1; i <= N; i++) tmp[cur][i] = 0;for (i = 1; i <= N; i++) {if (tmp[prev][i] == 0) continue;if (tmp[prev][i-1] > tmp[prev][i+1]) chmax(&(tmp[cur][i-1]), tmp[prev][i]);else chmax(&(tmp[cur][i+1]), tmp[prev][i]);}for (i = 1; i <= N; i = j) {if (tmp[cur][i] == 0) {j = i + 1;continue;}for (j = i + 1; j <= N && tmp[cur][j] != 0; j++);if (j - i > 2) break;}if (i > N) {prev ^= 1;break;}}for (i = 1; i <= N; i++) m[i] = tmp[prev][i];return k;}const int THR = 10;int main(){int i, j, k, l, N, m[200003], seed;scanf("%d", &N);for (i = 1; i <= N; i++) scanf("%d", &(m[i]));k = naive(N, m, THR);if (k <= THR) {for (i = 1, l = 0; i <= N; i = j) {if (m[i] == 0) j = i + 1;else {j = i + 2;l++;}}printf("%d %d\n", k, l);fflush(stdout);return 0;} else k--;int add = 0, p, max[2], argmax[2], tmp;for (i = 1, l = 0; i <= N; i = j) {if (m[i] == 0) {j = i + 1;continue;} else l++;max[0] = m[i];max[1] = m[i+1];argmax[0] = i;argmax[1] = i + 1;for (j = i + 2, p = 0; j <= N && m[j] != 0; j++, p ^= 1) {if (max[p] < m[j]) {max[p] = m[j];argmax[p] = j;}}if (argmax[0] < argmax[1]) {tmp = argmax[0] - i;chmax(&tmp, j - 1 - argmax[1]);chmax(&add, (argmax[1] - argmax[0]) / 2 + tmp);} else {tmp = argmax[1] - i;chmax(&tmp, j - 1 - argmax[0]);chmax(&add, (argmax[0] - argmax[1]) / 2 + tmp);}}printf("%d %d\n", k + add, l);fflush(stdout);return 0;}