結果
問題 | No.451 575 |
ユーザー | tnakao0123 |
提出日時 | 2016-12-02 17:54:36 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 2,316 bytes |
コンパイル時間 | 1,796 ms |
コンパイル使用メモリ | 83,248 KB |
実行使用メモリ | 5,168 KB |
最終ジャッジ日時 | 2023-08-22 13:37:24 |
合計ジャッジ時間 | 4,616 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 4 ms
4,376 KB |
testcase_07 | AC | 21 ms
5,168 KB |
testcase_08 | AC | 1 ms
4,376 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 10 ms
4,376 KB |
testcase_11 | AC | 26 ms
4,780 KB |
testcase_12 | AC | 33 ms
5,088 KB |
testcase_13 | AC | 33 ms
5,092 KB |
testcase_14 | AC | 2 ms
4,380 KB |
testcase_15 | AC | 3 ms
4,380 KB |
testcase_16 | AC | 5 ms
4,380 KB |
testcase_17 | AC | 21 ms
4,968 KB |
testcase_18 | AC | 21 ms
5,036 KB |
testcase_19 | AC | 14 ms
4,492 KB |
testcase_20 | AC | 3 ms
4,380 KB |
testcase_21 | AC | 2 ms
4,376 KB |
testcase_22 | AC | 1 ms
4,380 KB |
testcase_23 | AC | 33 ms
5,100 KB |
testcase_24 | AC | 16 ms
4,448 KB |
testcase_25 | AC | 1 ms
4,376 KB |
testcase_26 | AC | 2 ms
4,380 KB |
testcase_27 | AC | 2 ms
4,380 KB |
testcase_28 | AC | 1 ms
4,380 KB |
testcase_29 | AC | 4 ms
4,376 KB |
testcase_30 | AC | 22 ms
4,956 KB |
testcase_31 | AC | 1 ms
4,380 KB |
testcase_32 | AC | 7 ms
4,504 KB |
ソースコード
/* -*- coding: utf-8 -*- * * 451.cc: No.451 575 - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 100000; typedef long long ll; const ll LINF = 1LL << 62; const ll MIN_A = 1; const ll MAX_A = 1000000000000000000LL; /* typedef */ /* global variables */ ll as[MAX_N + 1], bs[MAX_N]; /* subroutines */ /* main */ // b_i = a_i + a_(i+1) (if i % 2 == 0) // b_i = a_i - a_(i+1) (if i % 2 == 1) // // a_(i+1) = b_i - a_i (if i % 2 == 0) // a_(i+1) = a_i - b_i (if i % 2 == 1) // // a0 = a0 // a1 = b0 - a0 // a2 = a1 - b1 = b0 - a0 - b1 = (b0-b1) - a0 // a3 = b2 - a2 = b2 - ((b0 - b1) - a0) = -b0+b1+b2 + a0 // a4 = a3 - b3 = -b0+b1+b2-b3 + a0 // a5 = b4 - a4 = b4 - (-b0+b1+b2-b3 + a0) = b0-b1-b2+b3+b4 - a0 // a6 = a5 - b5 = b0-b1-b2+b3+b4-b5 - a0 int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lld", &bs[i]); ll mina0 = LINF, maxa0 = -LINF, mina1 = 0, maxa1 = 0; as[0] = 0; for (int i = 0; i < n; i++) { as[i + 1] = ((i & 1) == 0) ? bs[i] - as[i] : as[i] - bs[i]; ll &ai = as[i + 1]; if ((i & 2) == 0) { if (mina0 > ai) mina0 = ai; if (maxa0 < ai) maxa0 = ai; } else { if (mina1 > ai) mina1 = ai; if (maxa1 < ai) maxa1 = ai; } } //printf("mina0=%lld, maxa0=%lld\n", mina0, maxa0); //printf("mina1=%lld, maxa1=%lld\n", mina1, maxa1); // 1 <= mina0 - a, maxa0 - a <= 10^18 // -> a <= mina0 - 1, a >= maxa0 - 10^18 // 1 <= mina1 + a, maxa1 + a <= 10^18 // -> a >= 1 - mina1, a <= 10^18 - maxa1 ll mina = MIN_A, maxa = MAX_A; if (mina < maxa0 - MAX_A) mina = maxa0 - MAX_A; if (maxa > mina0 - MIN_A) maxa = mina0 - MIN_A; if (mina < MIN_A - mina1) mina = MIN_A - mina1; if (maxa > MAX_A - maxa1) maxa = MAX_A - maxa1; //printf("mina=%lld, maxa=%lld\n", mina, maxa); if (mina > maxa) puts("-1"); else { printf("%d\n%lld\n", n + 1, mina); for (int i = 0; i < n; i++) printf("%lld\n", as[i + 1] + mina * (((i & 2) == 0) ? -1 : 1)); } return 0; }