//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
*/
# |
Verdict |
Execution time |
Memory |
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 |
- |
# |
Verdict |
Execution time |
Memory |
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 |
- |
# |
Verdict |
Execution time |
Memory |
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 |
- |