Submission #963015

#	Time	Username	Problem	Language	Result	Execution time	Memory
963015		Unforgettablepl	Remittance (JOI19_remittance)	C++17	55 / 100	20 ms	8100 KiB

remittance

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int modulo = 1e9+7;

int A[100001];
int B[100001];
int curr[100001];
int arr[100001];

int inv(int a){
    int p = modulo-2;
    int ans = 1;
    while(p){
        if(p&1){
            ans*=a;
            ans%=modulo;
            p--;
        }
        a*=a;
        a%=modulo;
        p/=2;
    }
    return ans;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i=0;i<n;i++)cin>>A[i]>>B[i];
    int start = 0;
    int power = 1;
    for(int i=1;i<n;i++){
        start=(start+modulo+((power*(A[i]-B[i]))%modulo))%modulo;
        power*=2ll;
        power%=modulo;
        start%=modulo;
    }
    start=(start+modulo+((power*(A[0]-B[0]))%modulo))%modulo;
    power*=2ll;
    power%=modulo;
    start%=modulo;
    power+=modulo-1;
    power%=modulo;
    start=(start*inv(power))%modulo;
    arr[0]=start;
    bool works = true;
    if(start<0)works=false;
    for(int x=1;x<n;x++){
        arr[x]=arr[x-1]+A[x]-B[x];
        if(arr[x]<0)works=false;
        if(arr[x]&1)works=false;
        arr[x]/=2;
    }
    int backup = arr[n-1]+A[0]-B[0];
    if(backup&1)works=false;
    if(arr[0]!=backup/2)works=false;
    if(!works)goto shit;
    for(int x=0;x<n;x++)curr[x]=A[x];
    for(int rounds=1;rounds<40;rounds++){
        for(int x=0;x<n;x++){
            int uses = min(arr[x],curr[x]/2);
            curr[x]-=2*uses;
            arr[x]-=uses;
            curr[(x+1)%n]+=uses;
        }
    }
    for(int x=0;x<n;x++)if(curr[x]!=B[x])works=false;
    if(works){
        cout << "Yes\n";
        return 0;
    }
    shit:
    cout << "No\n";
}

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