Submission #489476

#	Time	Username	Problem	Language	Result	Execution time	Memory
489476		8e7	송금 (JOI19_remittance)	C++17	100 / 100	234 ms	52100 KiB

remittance

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
void debug(){cout << endl;}
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 1000005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
ll a[maxn], b[maxn], c[maxn], ans[maxn];
bool check(int n, ll num) {
	ans[n-1] = num;
	for (int i = 0;i < n - 1;i++) {
		if ((ans[(i+n-1)%n] - c[i]) % 2) return 0;
		ans[i] = (ans[(i+n-1)%n] - c[i]) / 2;
		//debug(i, ans[i]);
	}
	return (ans[n-2] - 2 * ans[n-1] == c[n-1]);
}
int main() {
	io
	int n;
	cin >> n;
	
	for (int i = 0;i < n;i++) {
		cin >> a[i] >> b[i];	
		c[i] = b[i] - a[i];
	}
	ll sum = 0, cnt = 0;
	ll cur = 1;
	for (int i = max(0, n - 30);i < n;i++) {
		sum += cur * c[i];
		cur *= 2;
	}
	ll val = (-sum) / (cur - 1);
	if (!check(n, val)) {
		if (!check(n, val - 1)) {
			check(n, val + 1);
		}
	}
	
	for (int i = 0;i < n;i++) {
		cnt += ans[i];
		if (ans[i] < 0) {
			cout << "No\n";
			return 0;
		}
	}
	cur = 0;
	ll prv = n-1;
	while (cnt > 0) {
		int dif = min(ans[cur], a[cur]/2);	
		ans[cur] -= dif, a[cur] -= dif*2;
		a[(cur+1)%n] += dif;	
		cnt -= dif;
		if (dif > 0) {
			prv = cur;
		} else if (cur == prv) {
			cout << "No\n";
			return 0;
		}
		cur = (cur + 1) % n;
	}
	for (int i = 0;i < n;i++) {
		if (a[i] != b[i]) {
			cout << "No\n";
			return 0;
		}
	}
	cout << "Yes\n";
	return 0;

}
/*
5
0 0
1 0
2 3
3 3
4 0
*/

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