| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 893732 | Alcabel | 송금 (JOI19_remittance) | C++17 | 0 ms | 0 KiB |
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;
#ifdef LOCAL
const long long mod = 1e9 + 7;
#else
const long long mod = 2000000000000021ll;
#endif
#ifdef LOCAL
typedef long long __int128_t;
#endif
struct Modint {
long long x;
Modint() {
x = 0;
}
Modint(long long _x) {
while (_x >= mod) {
_x -= mod;
}
while (_x < 0) {
_x += mod;
}
x = _x;
}
Modint(__int128_t _x) {
if (_x >= mod || _x <= -mod) {
_x %= mod;
}
if (_x < 0) {
_x += mod;
}
x = _x;
}
Modint operator+(const Modint& other) const {
return Modint(x + other.x);
}
Modint operator-(const Modint& other) const {
return Modint(x - other.x);
}
Modint operator*(const Modint& other) const {
return Modint((__int128_t)x * other.x);
}
void operator+=(const Modint& other) {
*this = *this + other;
}
void operator-=(const Modint& other) {
*this = *this - other;
}
void operator*=(const Modint& other) {
*this = *this * other;
}
Modint operator^(long long k) const {
Modint tmp = x, res = 1;
while (k > 0) {
// cerr << k << '\n';
if (k & 1ll) {
res *= tmp;
}
tmp *= tmp;
k >>= 1;
}
return res;
}
~Modint() {}
};
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
}
Modint denom = 1;
for (int i = 0; i < n; ++i) {
denom = denom + denom;
}
// cerr << denom.x << '\n';
denom = (denom - 1) ^ (mod - 2);
// cerr << (denom * ((1ll << n) - 1)).x << '\n';
vector<long long> x(n);
for (int i = 0; i < n; ++i) {
Modint xmod = 0;
for (int j = i; j >= 0; --j) {
xmod = xmod + xmod + b[j] - a[j];
}
for (int j = n - 1; j > i; --j) {
xmod = xmod + xmod + b[j] - a[j];
}
xmod = (Modint(0) - xmod) * denom;
if (xmod.x > mod / 2) {
cout << "No\n";
return;
}
x[i] = xmod.x;
}
for (int i = 0, prv = n - 1; i < n; ++i, ++prv) {
if (prv == n) { prv = 0; }
if (x[prv] - 2 * x[i] != b[i] - a[i]) {
cout << "No\n";
return;
}
}
bool change = true;
while (change) {
change = false;
for (int i = 0; i < n; ++i) {
if (x[i] > 0 && a[i] >= 2) {
change = true;
long long trans = min(x[i], a[i] * 1ll / 2);
x[i] -= trans;
a[i] -= 2 * trans;
int nxt = i + 1;
if (nxt == n) {
nxt = 0;
}
a[nxt] += trans;
}
}
}
for (int i = 0; i < n; ++i) {
if (x[i] != 0) {
cout << "No\n";
return;
}
}
cout << "Yes\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
/*
2000000000000021
2000000000000077
2000000000000081
*/