CODE FESTIVAL 2016 Elimination Tournament Round 2 (Parallel)

Submission #1227643

Source codeソースコード

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
int MX=100000;
int N,M;
ll o[1000][1000];
ll inf = 1e13;
vector<ll> getnext(vector<ll> a){
	int N = a.size();
	vector<ll> b(N);
	rep(i,N) b[i]=a[i];
	rep(i,N-1) b[i+1]+=b[i];
	return b;
}
ll need(vector<ll> a,vector<ll> b){	//need b++
	if(a[0]<b[0]) return -inf;
	assert(a[0]==b[0]);
	int N = a.size();

	if(a>=b){
		ll nd = (a[1]-b[1]+b[0]-1)/b[0];
		if(a[1]<nd*b[0]+b[1]) return nd;
		assert(a[1]==nd*b[0]+b[1]);
		if(N==2) return nd+1;

		ll nb2 = b[2] + nd*b[1] + nd*(nd+1)/2*b[2];
		if(nb2>a[2]) return nd;

		//assert(nd<=10000)
		rep(t,10000000){
			if(a<b) return t;
			b = getnext(b);
		}
	}else{
		return -need(b,a);
	}
}
ll ns[1000];
ll solve(){
	cin>>N>>M;
	rep(i,N) rep(j,M) cin>>o[i][j];
	if(N==1){
		return 0;
	}
	rep(i,N-1) if(o[i][0]>o[i+1][0]){
		return -1;
	}
	if(M==1){
		rep(i,N-1) if(o[i][0]==o[i+1][0]){
			return -1;
		}
		return 0;
	}

	rep(i,N-1){
		vector<ll> a(M),b(M);
		rep(j,M) a[j]=o[i][j],b[j]=o[i+1][j];
		ns[i] = need(a,b);
//		show(ns[i]);
		assert(ns[i]!=inf);
	}

	ll ans = 0;
	ll prev = 0;
	rep(i,N-1){
		ll nd = ns[i] + prev;
		if(nd<0) nd=0;
		ans+=nd;
		prev=nd;
	}
	return ans;
}
int main(){
	cout<<solve()<<endl;
}

Submission

Task問題 B - 魔法使い高橋君 / Takahashi the Magician
User nameユーザ名 025_sigma
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 1868 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_1.txt,sample_2.txt,sample_3.txt
subtask1 0 / 200 sample_1.txt,sample_3.txt,hack_1.txt,hack_2.txt,hack_3.txt,hack_4.txt,hack_5.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_12.txt,subtask_1_13.txt,subtask_1_14.txt,subtask_1_15.txt,subtask_1_16.txt,subtask_1_17.txt,subtask_1_18.txt,subtask_1_19.txt,subtask_1_2.txt,subtask_1_20.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt
subtask2 0 / 800 sample_1.txt,sample_2.txt,sample_3.txt,hack_1.txt,hack_2.txt,hack_3.txt,hack_4.txt,hack_5.txt,subtask_2_1.txt,subtask_2_10.txt,subtask_2_11.txt,subtask_2_12.txt,subtask_2_13.txt,subtask_2_14.txt,subtask_2_15.txt,subtask_2_16.txt,subtask_2_17.txt,subtask_2_18.txt,subtask_2_19.txt,subtask_2_2.txt,subtask_2_20.txt,subtask_2_21.txt,subtask_2_22.txt,subtask_2_23.txt,subtask_2_24.txt,subtask_2_25.txt,subtask_2_26.txt,subtask_2_27.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt,subtask_2_9.txt
All 0 / 200 sample_1.txt,sample_2.txt,sample_3.txt,hack_1.txt,hack_2.txt,hack_3.txt,hack_4.txt,hack_5.txt,sample_1.txt,sample_2.txt,sample_3.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_12.txt,subtask_1_13.txt,subtask_1_14.txt,subtask_1_15.txt,subtask_1_16.txt,subtask_1_17.txt,subtask_1_18.txt,subtask_1_19.txt,subtask_1_2.txt,subtask_1_20.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt,subtask_2_1.txt,subtask_2_10.txt,subtask_2_11.txt,subtask_2_12.txt,subtask_2_13.txt,subtask_2_14.txt,subtask_2_15.txt,subtask_2_16.txt,subtask_2_17.txt,subtask_2_18.txt,subtask_2_19.txt,subtask_2_2.txt,subtask_2_20.txt,subtask_2_21.txt,subtask_2_22.txt,subtask_2_23.txt,subtask_2_24.txt,subtask_2_25.txt,subtask_2_26.txt,subtask_2_27.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt,subtask_2_9.txt,subtask_3_1.txt,subtask_3_10.txt,subtask_3_11.txt,subtask_3_12.txt,subtask_3_13.txt,subtask_3_14.txt,subtask_3_2.txt,subtask_3_3.txt,subtask_3_4.txt,subtask_3_5.txt,subtask_3_6.txt,subtask_3_7.txt,subtask_3_8.txt,subtask_3_9.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
hack_1.txt WA
hack_2.txt WA
hack_3.txt WA
hack_4.txt AC 1 ms 256 KB
hack_5.txt WA
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt WA
subtask_1_1.txt WA
subtask_1_10.txt WA
subtask_1_11.txt WA
subtask_1_12.txt WA
subtask_1_13.txt WA
subtask_1_14.txt WA
subtask_1_15.txt WA
subtask_1_16.txt AC 387 ms 8064 KB
subtask_1_17.txt AC 388 ms 8064 KB
subtask_1_18.txt WA
subtask_1_19.txt WA
subtask_1_2.txt AC 1 ms 256 KB
subtask_1_20.txt AC 3 ms 6272 KB
subtask_1_3.txt AC 2 ms 640 KB
subtask_1_4.txt WA
subtask_1_5.txt WA
subtask_1_6.txt WA
subtask_1_7.txt WA
subtask_1_8.txt WA
subtask_1_9.txt WA
subtask_2_1.txt WA
subtask_2_10.txt WA
subtask_2_11.txt AC 184 ms 8064 KB
subtask_2_12.txt WA
subtask_2_13.txt WA
subtask_2_14.txt WA
subtask_2_15.txt WA
subtask_2_16.txt AC 178 ms 8064 KB
subtask_2_17.txt AC 177 ms 8064 KB
subtask_2_18.txt WA
subtask_2_19.txt AC 3 ms 6272 KB
subtask_2_2.txt WA
subtask_2_20.txt WA
subtask_2_21.txt WA
subtask_2_22.txt WA
subtask_2_23.txt WA
subtask_2_24.txt WA
subtask_2_25.txt WA
subtask_2_26.txt WA
subtask_2_27.txt WA
subtask_2_3.txt WA
subtask_2_4.txt WA
subtask_2_5.txt WA
subtask_2_6.txt AC 184 ms 8064 KB
subtask_2_7.txt WA
subtask_2_8.txt WA
subtask_2_9.txt WA
subtask_3_1.txt WA
subtask_3_10.txt WA
subtask_3_11.txt WA
subtask_3_12.txt AC 386 ms 8064 KB
subtask_3_13.txt WA
subtask_3_14.txt AC 3 ms 6272 KB
subtask_3_2.txt WA
subtask_3_3.txt WA
subtask_3_4.txt AC 391 ms 8064 KB
subtask_3_5.txt TLE
subtask_3_6.txt AC 393 ms 8064 KB
subtask_3_7.txt WA
subtask_3_8.txt WA
subtask_3_9.txt TLE