結果

問題 No.451 575
コンテスト
ユーザー tnakao0123
提出日時 2016-12-02 17:54:36
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 33 ms / 2,000 ms
コード長 2,316 bytes
コンパイル時間 771 ms
コンパイル使用メモリ 84,436 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-16 11:04:10
合計ジャッジ時間 3,148 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:62:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   62 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
main.cpp:63:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   63 |   for (int i = 0; i < n; i++) scanf("%lld", &bs[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~~

ソースコード

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