結果

問題 No.451 575
ユーザー tnakao0123tnakao0123
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- 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;
}
0