Submission #893752

#TimeUsernameProblemLanguageResultExecution timeMemory
893752AlcabelRemittance (JOI19_remittance)C++17
100 / 100
241 ms59996 KiB
#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 = 0ll; } 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 = 1ll; 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 = 1ll; for (int i = 0; i < n; ++i) { denom = denom + denom; } // cerr << denom.x << '\n'; denom = (denom - 1ll) ^ (mod - 2); // cerr << (denom * ((1ll << n) - 1)).x << '\n'; vector<Modint> two(n + 1); two[0] = 1ll; for (int i = 1; i <= n; ++i) { two[i] = two[i - 1] + two[i - 1]; // cerr << "i: " << i << ", two: " << two[i].x << '\n'; } vector<Modint> pref(n + 1), suf(n + 1); for (int i = 1; i <= n; ++i) { pref[i] = pref[i - 1] + two[i - 1] * (long long)(b[i - 1] - a[i - 1]); } for (int i = n - 1; i >= 0; --i) { suf[i] = suf[i + 1] + suf[i + 1] + (long long)(b[i] - a[i]); // cerr << "i: " << i << ", suf: " << suf[i].x << '\n'; } vector<long long> x(n); for (int i = 0; i < n; ++i) { Modint xmod = pref[i + 1] * two[n - i - 1] + suf[i + 1]; /*for (int j = i; j >= 0; --j) { xmod = xmod + xmod + (long long)(b[j] - a[j]); } for (int j = n - 1; j > i; --j) { xmod = xmod + xmod + (long long)(b[j] - a[j]); }*/ xmod = (Modint(0ll) - 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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...