Submission #347109

#	Time	Username	Problem	Language	Result	Execution time	Memory
347109		wwdd	Remittance (JOI19_remittance)	C++14	0 / 100	1095 ms	364 KiB

remittance

//this is way too gross
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
const ll LIM = 1e12;
vl wa,wb;
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll n;
	cin >> n;
	vl di;
	for(int i=0;i<n;i++) {
		ll a,b;
		cin >> a >> b;
		wa.push_back(a);
		wb.push_back(b);
		di.push_back(a-b);
	}
	ll st = 0,ed = 1e9+10;
	ll suc = -1;
	bool poss = false;
	vl go(n,-1);
	while(st <= ed) {
		ll m = (st+ed)/2;
		ll dif = m-di.back();
		go.back() = m;
		for(int i=n-2;i>=0;i--) {
			go[i] = m+dif;
			dif = m-(di[i]-2*dif);
			dif = min(dif,LIM);
			dif = max(dif,-LIM);
		}
		if(dif > 0) {
			ed = m-1;
		} else if(dif < 0) {
			st = m+1;
		} else {
			suc = m;
			poss = true;break;
		}
	}
	ll rus = 0;
	ll rup = 0;
	for(int i=0;i<n;i++) {
		rus += wb[i];
		rup += go[i];
		if(go[i] < 0) {
			poss = false;
		}
	}
	/*
	if(rus == 0) {
		poss = false;
	}
	*/
	if(!poss) {
		cout << "No\n";
	} else {
		int pt = 0;
		while(rup > 0) {
			int nx = pt+1;
			if(nx >= n) {nx -= n;}
			ll mo = min(wa[pt]/2,go[pt]);
			wa[pt] -= 2*mo;
			wa[nx] += mo;
			go[pt] -= mo;
			pt = nx;
			rup -= mo;
		}
		for(int i=0;i<n;i++) {
			if(wa[i] != wb[i]) {
				poss = false;
			}
		}
		if(poss) {
			cout << "Yes\n";
		} else {
			cout << "No\n";
		}
	}
}

Compilation message (stderr)

remittance.cpp: In function 'int main()':
remittance.cpp:21:5: warning: variable 'suc' set but not used [-Wunused-but-set-variable]
   21 |  ll suc = -1;
      |     ^~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 45