This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define endl '\n'
#define pb push_back
using pi = array<int, 2>;
const int N = 1e6 + 5, MOD = 1e9 + 7;
int p2[N];
void prec() {
p2[0] = 1;
for (int i = 1; i < N; ++i) p2[i] = p2[i - 1] * 2 % MOD;
}
int binpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
int modinv(int n) {
return binpow(n, MOD - 2);
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
prec();
int n;
cin >> n;
vector<int> a(n), b(n), c(n);
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
c[i] = b[i] - a[i];
}
vector<int> in(n);
for (int i = 0; i < n; ++i) {
in[0] = (in[0] - p2[i] * c[i] % MOD + MOD) % MOD;
}
in[0] = (in[0] * modinv(p2[n] - 1) % MOD + MOD) % MOD;
for (int i = 1; i < n; ++i) {
int x = in[i - 1] - c[i - 1];
if (x % 2 != 0) {
cout << "No";
return 0;
}
in[i] = x / 2;
}
for (int i = 0; i < n; ++i) {
if (in[i] < 0) {
cout << "No";
return 0;
}
}
bool pushed = true;
while (pushed) {
pushed = false;
for (int i = 0; i < n; ++i) {
int j = (i + 1) % n;
int push = min(in[j], a[i] / 2);
a[i] -= 2 * push;
in[j] -= push;
a[j] += push;
if (push != 0) pushed = true;
}
}
for (int i = 0; i < n; ++i) {
if (in[i] != 0) {
cout << "No";
return 0;
}
}
cout << "Yes";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |