結果
問題 | No.451 575 |
ユーザー |
|
提出日時 | 2016-12-05 10:38:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 138 ms / 2,000 ms |
コード長 | 2,131 bytes |
コンパイル時間 | 1,685 ms |
コンパイル使用メモリ | 171,308 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-17 12:42:12 |
合計ジャッジ時間 | 4,611 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll INF = 1000000000000000001;int main() {cin.tie(0);ios::sync_with_stdio(false);int n;cin >> n;vector<ll> b(n);for (int i = 0; i < n; i++) cin >> b[i];//b[i] = a[0] +- a[i]とするfor (int i = 1; i < n; i++) {if ((i - 1) / 2 % 2 == 0) {b[i] = b[i - 1] - b[i];} else {b[i] += b[i - 1];}}//上よりa[i] = a[0] - b[i] または b[i] - a[0]//a[i]が最小値となるようなiの候補は//1. a[i] = a[0] - b[i]を満たすiについてb[i]が最大となるようなi//2. a[i] = b[i] - a[0]を満たすiについてb[i]が最小となるようなi//よって以上の2つのiについてa[i]=1として調べる(もっと簡単な解法がある気がする)ll Min = INF, Max = 0;int imin = -1, imax = -1;for (int i = 0; i < n; i++) {if (i / 2 % 2 == 0) {if (Min > b[i]) {Min = b[i];imin = i + 1;}} else {if (Max < b[i]) {Max = b[i];imax = i + 1;}}}bool flag;//候補1if (imin != -1) {vector<ll> a1(n + 1);a1[imin] = 1;a1[0] = b[imin - 1] - a1[imin];flag = true;if (a1[0] <= 0 || a1[0] >= INF) flag = false;for (int i = 0; i < n; i++) {if (i / 2 % 2 == 0) {a1[i + 1] = b[i] - a1[0];} else {a1[i + 1] = -b[i] + a1[0];}if (a1[i + 1] <= 0 || a1[i + 1] >= INF) {flag = false;break;}}if (flag) {cout << n + 1 << endl;for (int i = 0; i <= n; i++) {cout << a1[i] << endl;}return 0;}}//候補2if (imax != -1) {vector<ll> a2(n + 1);a2[imax] = 1;a2[0] = -b[imax - 1] + a2[imax];flag = true;if (a2[0] <= 0 || a2[0] >= INF) flag = false;for (int i = 0; i < n; i++) {if (i / 2 % 2 == 0) {a2[i + 1] = b[i] - a2[0];} else {a2[i + 1] = -b[i] + a2[0];}if (a2[i + 1] <= 0 || a2[i + 1] >= INF) {flag = false;break;}}if (flag) {cout << n + 1 << endl;for (int i = 0; i <= n; i++) {cout << a2[i] << endl;}return 0;}}cout << -1 << endl;return 0;}