제출 #666175

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
666175		ParsaS	송금 (JOI19_remittance)	C++17	100 / 100	255 ms	52124 KiB

remittance

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
#define int ll
const int N = 1e6 + 5;
const int MOD = 2e9 + 11;
int pw[N], d[N], A[N], B[N], x[N];

int binpow(int a, int b) {
    return b ? 1LL * binpow(1LL * a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD : 1;
}
void solve() {
    pw[0] = 1;
    for (int i = 1; i < N; i++)
        pw[i] = 2LL * pw[i - 1] % MOD;
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b; cin >> a >> b;
        A[i] = a, B[i] = b;
        d[i] = a - b;
    }
    int r = 1LL * pw[n - 1] * (d[0] + MOD) % MOD;
    for (int i = 1; i < n; i++) {
        r = (r + 1LL * pw[i - 1] * (1LL * d[i] + MOD) % MOD) % MOD;
    }
    r = 1LL * r * binpow(pw[n] - 1, MOD - 2) % MOD;
    bool ok = true;
    x[0] = r;
    for (int i = 1; i < n; i++) {
        x[i] = (x[i - 1] + d[i]) / 2;
    }
    for (int i = 0; i < n; i++) {
        int j = (i + n - 1) % n;
        ok &= x[i] >= 0 && A[i] - B[i] == 2 * x[i] - x[j];
    }
    bool f = false;
    for (int k = 0; k < 5 && !f; k++) {
        for (int i = 0; i < n; i++) {
            int c = min(A[i] / 2, x[i]);
            A[i] -= 2 * c, x[i] -= c;
            A[(i + 1) % n] += c;
            if (x[i] == 0) {
                f = true;
                break;
            }
        }
    }
    int st = 0;
    for (st; st < n && x[st] > 0; st++);
    ok &= st < n;
    for (int i = (st + 1) % n; ok && i != st; i = (i + 1) % n) {
        ok &= A[i] / 2 >= x[i];
        A[i] -= x[i] * 2;
        A[(i + 1) % n] += x[i];
    }
    cout << (ok ? "Yes" : "No") << '\n';

}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    solve();

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

remittance.cpp: In function 'void solve()':
remittance.cpp:54:10: warning: statement has no effect [-Wunused-value]
   54 |     for (st; st < n && x[st] > 0; st++);
      |          ^~

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45