結果
問題 | No.451 575 |
ユーザー |
![]() |
提出日時 | 2017-02-04 12:14:16 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 87 ms / 2,000 ms |
コード長 | 5,753 bytes |
コンパイル時間 | 1,649 ms |
コンパイル使用メモリ | 120,964 KB |
実行使用メモリ | 17,280 KB |
最終ジャッジ日時 | 2024-12-24 06:11:25 |
合計ジャッジ時間 | 4,662 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
コンパイルメッセージ
In file included from /usr/include/c++/11/bits/char_traits.h:39, from /usr/include/c++/11/ios:40, from /usr/include/c++/11/ostream:38, from /usr/include/c++/11/iostream:39, from main.cpp:8: In static member function ‘static _Tp* std::__copy_move<_IsMove, true, std::random_access_iterator_tag>::__copy_m(const _Tp*, const _Tp*, _Tp*) [with _Tp = long long int; bool _IsMove = false]’, inlined from ‘_OI std::__copy_move_a2(_II, _II, _OI) [with bool _IsMove = false; _II = long long int*; _OI = long long int*]’ at /usr/include/c++/11/bits/stl_algobase.h:495:30, inlined from ‘_OI std::__copy_move_a1(_II, _II, _OI) [with bool _IsMove = false; _II = long long int*; _OI = long long int*]’ at /usr/include/c++/11/bits/stl_algobase.h:522:42, inlined from ‘_OI std::__copy_move_a(_II, _II, _OI) [with bool _IsMove = false; _II = long long int*; _OI = long long int*]’ at /usr/include/c++/11/bits/stl_algobase.h:529:31, inlined from ‘_OI std::copy(_II, _II, _OI) [with _II = long long int*; _OI = long long int*]’ at /usr/include/c++/11/bits/stl_algobase.h:620:7, inlined from ‘static _ForwardIterator std::__uninitialized_copy<true>::__uninit_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = long long int*; _ForwardIterator = long long int*]’ at /usr/include/c++/11/bits/stl_uninitialized.h:110:27, inlined from ‘_ForwardIterator std::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = long long int*; _ForwardIterator = long long int*]’ at /usr/include/c++/11/bits/stl_uninitialized.h:151:15, inlined from ‘_ForwardIterator std::__uninitialized_copy_a(_InputIterator, _InputIterator, _ForwardIterator, std::allocator<_Tp>&) [with _InputIterator = long long int*; _ForwardIterator = long long int*; _Tp = long long int]’ at /usr/include/c++/11/bits/stl_uninitialized.h:333:37, inlined from ‘std::vec
ソースコード
#ifdef __GNUC__#pragma GCC optimize ("O3")#pragma GCC target ("avx")#endif#define _USE_MATH_DEFINES#include <iostream>#include <iomanip>#include <stdio.h>#include <sstream>#include <algorithm>#include <cmath>#include <string>#include <cstring>#include <vector>#include <valarray>#include <array>#include <queue>#include <complex>#include <set>#include <map>#include <stack>#include <list>#include <cassert>//assert();#include <fstream>/////////#define REP(i, x, n) for(int i = x; i < n; i++)#define rep(i,n) REP(i,0,n)/////////typedef long long LL;typedef long double LD;typedef unsigned long long ULL;#define PII pair<int,int>/////////using namespace::std;// 最大公約数template<class T>inline T gcd(T a, T b){return b == 0 ? a : gcd(b, a % b);}// 最小公倍数template<class T>inline T lcm(T a, T b){return a * b / gcd(a, b);}////////////////////////////////const LL NUM_MAX = 10000000000;struct bnum{bool neg;vector<LL> num;void set(ULL X){neg = false;num.resize(2);num[1] = X/NUM_MAX;num[0] = X%NUM_MAX;}inline bnum operator=(int X){bnum ret;ret.neg = X<0;ret.num.resize(2);ret.num[1] = X/NUM_MAX;ret.num[0] = X%NUM_MAX;return ret;}/*(+)+(+)=A+B(+)+(-)=A-B(-)+(+)=B-A(-)+(-)=-(A+B)(+)-(+)=A-B(+)-(-)=A+B(-)-(+)=-(A+B)(-)-(-)=B-A*/inline bnum& operator=(bnum X){num = vector<LL>(2);neg = X.neg;num = X.num;return *this;}inline bnum& operator=(bnum *P){neg = P->neg;num = P->num;return *this;}inline bnum operator-(){bnum ret;ret.neg = !neg;ret.num = num;return ret;}bnum operator+(bnum X){bnum ret;ret.neg = neg;ret.num = num;if( ret.neg == X.neg ){ret = add(ret,X);ret.neg = X.neg;return ret;}if( ret.neg == true){ret.neg = false;return X-ret;}else if( X.neg == true ){return ret-X;}return ret;//dum}bnum operator-(bnum X){bnum ret;ret.neg = neg;ret.num = num;if( X.neg == true ){X.neg = false;return ret+X;}//X>=0if( ret.neg == false && X.neg == false ){if( eq(ret,X) ){ret.set(0);return ret;}if( ABSlar(ret,X) ){if( ret.num[0] < X.num[0] ){ret.num[1]--;ret.num[0] += NUM_MAX;}ret.num[0] = ret.num[0]-X.num[0];ret.num[1] = ret.num[1]-X.num[1];return ret;}else{ret = X-ret;ret.neg = true;}}else{//ret<0 X>0ret = add(ret,X);ret.neg = true;}return ret;}bnum add(bnum A,bnum B){bnum ret;ret.neg = false;//指定しないret.num.resize(2);ret.num[0] = 0;ret.num[1] = 0;ret.num[0] = A.num[0]+B.num[0];if( ret.num[0] >= NUM_MAX ){ret.num[0] -= NUM_MAX;ret.num[1] += 1;}ret.num[1] += A.num[1]+B.num[1];return ret;}bnum sub(bnum A,bnum B){//同符号として値だけ引くA-Bbnum ret;ret.num.resize(2);if( ABSlar(A,B) ){//A-B->+ret.neg = false;if( A.num[0] < B.num[0] ){A.num[1]--;A.num[0] += NUM_MAX;}ret.num[0] = A.num[0]-B.num[0];ret.num[1] = A.num[1]-B.num[0];return ret;}else{ret = sub(B,A);ret.neg = true;return ret;}}//|A|>|B|bool ABSlar(const bnum A,const bnum B){if( A.num[1] > B.num[1] ){return true;}else if(A,num[1] < B.num[1]){return false;}if( A.num[0] > B.num[0] ){return true;}return false;}inline bool eq(bnum A,bnum B){if( A.num[0]==0 && A.num[1] ==0 &&B.num[0]==0 && B.num[1] == 0){return true;}if( A.num == B.num && A.neg==B.neg){return true;}return false;}bool operator<(bnum B){bnum temp;temp.neg = neg;temp.num = num;if( neg == B.neg ){if( neg == false ){return ABSlar(B,temp);}else{return ABSlar(temp,B);}}if( eq(temp,B) ){return false;}if( temp.neg == false ){return false;}else if( B.neg == false){return true;}return false;//dum}inline bool operator>(bnum B){bnum temp;temp.neg = neg;temp.num = num;return B<temp;}inline bool operator<=(bnum B){bnum temp;temp.neg = neg;temp.num = num;return !(temp>B);}inline bool operator>=(bnum B){bnum temp;temp.neg = neg;temp.num = num;return !(temp<B);}};const ULL MAX_A = (ULL)1000000000000000000;inline void solve(){int N;cin >> N;vector<ULL> B(N+1);vector<bnum> Bnum(N+1);for(int i=1;i<=N;++i){cin >> B[i];Bnum[i].set(B[i]);}vector<ULL> A(N+2,0);vector<bnum> Anum(N+2);for(int i=0;i<N+2;++i){Anum[i] = 0;}Anum[1].set(1);for(int i=1;i<=N;++i){if(i%2 == 1){Anum[i+1] = Bnum[i]-Anum[i];}else{Anum[i+1] = Anum[i]-Bnum[i];}}ULL A1,AA,BB;A1 = 1;bnum negMax;negMax.set(1);for(int i=1;i<=N+1;++i){if( negMax > Anum[i] ){negMax = Anum[i];A1 = 2+negMax.num[0]+negMax.num[1]*NUM_MAX;}}A[1] = A1;//A1からAを作るfor(int i=1;i<=N;++i){if( i%2 == 1 ){A[i+1] = B[i]-A[i];}else{A[i+1] = A[i]-B[i];}}//チェックfor(int i=1;i<=N+1;++i){AA = A[i];if( AA == 0 || MAX_A < AA ){cout << -1 << endl;return;}}for(int i=1;i<=N;++i){if(i%2 == 1){AA = A[i]+A[i+1];BB = B[i];if( BB != AA || AA < A[i] || AA < A[i+1] ){cout << -1 << endl;return;}}else{AA = A[i]-A[i+1];BB = B[i];ULL A_1,A_2;A_1 = A[i];A_2 = A[i+1];if( BB != AA || A_2 >= A_1 ){cout << -1 << endl;return;}}}//出力{cout << N+1 << '\n';for(int i=1;i<=N+1;++i){cout << A[i] << '\n';}cout << flush;}}signed main(void){std::cin.tie(0);std::ios::sync_with_stdio(false);//std::cout << std::fixed;//小数を10進数表示//cout << setprecision(16);//小数をいっぱい表示する。16?solve();}