Submission #677647

#	Time	Username	Problem	Language	Result	Execution time	Memory
677647		Cross_Ratio	Remittance (JOI19_remittance)	C++14	0 / 100	1 ms	212 KiB

remittance

#include <bits/stdc++.h>
#define int long long
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];
    priority_queue<P> PQ;
    for(i=0;i<N;i++) {
        if(A[i] > B[i]+1) {
            PQ.push(P(A[i] - B[i], i));
        }
    }
    while(!PQ.empty()) {
        P k = PQ.top();
        PQ.pop();
        int id = k.second;
        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) {
            PQ.push(P(A[(id+1)%N]-B[(id+1)%N], (id+1)%N));
        }
    }
    bool isPos1 = true;
    bool 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:13:12: warning: unused variable 'j' [-Wunused-variable]
   13 |     int i, j;
      |            ^

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