oj.uz

답안 #489475

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
489475 2021-11-23T03:18:38 Z 8e7 송금 (JOI19_remittance) C++17
0 / 100
 1 ms 332 KB 
//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] % 2 != 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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -