Submission #677657

#	Time	Username	Problem	Language	Result	Execution time	Memory
677657		Cross_Ratio	Remittance (JOI19_remittance)	C++14	100 / 100	301 ms	32640 KiB

remittance

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int A[1000005];
int B[1000005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    int i, j;
    for(i=0;i<N;i++) cin >> A[i] >> B[i];
    queue<int> Q;
    for(i=0;i<N;i++) {
        if(A[i] > B[i]+1) {
            Q.push(i);
        }
    }
    while(!Q.empty()) {
        int id = Q.front();
        Q.pop();
        if(A[id] <= B[id]+1) continue;
        int v = A[id] - B[id];
        v /= 2;
        A[id] -= v*2;
        A[(id+1)%N] += v;
        if(A[(id+1)%N]>B[(id+1)%N]+1) {
            Q.push((id+1)%N);
        }
    }
    bool isPos1 = true;
    bool isPos2 = false;
    for(i=0;i<N;i++) {
        if(A[i]>=2) isPos2 = true;
    }
    for(i=0;i<N;i++) {
        if(A[i]!=B[i]) isPos1 = false;
        if(A[i]!=B[i]+1) isPos2 = false;
        assert(A[i]<B[i]+2);
    }

    cout << (isPos1||isPos2?"Yes":"No");
}

Compilation message (stderr)

remittance.cpp: In function 'int main()':
remittance.cpp:12:12: warning: unused variable 'j' [-Wunused-variable]
   12 |     int i, j;
      |            ^

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