Submission #1145540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145540		keisuke6	Remittance (JOI19_remittance)	C++20	55 / 100	1098 ms	94372 KiB

remittance

#include <bits/stdc++.h>
using namespace std;
#define int long long
int mod1 = 998244353, mod2 = 968244353;
int modpow(int a, int x, int mod){
    int ans = 1, now = a;
    x %= mod-1;
    for(int i=0;i<30;i++){
        if(x&(1<<i)) ans = (ans*now)%mod;
        now = now*now%mod;
    }
    return ans;
}
int modinv(int a, int mod){
    return modpow(a,mod-2,mod);
}
int f(int a, int m1, int b, int m2){
    int t = m1-m2;
    int d = (b > a%m2 ? b-(a%m2) : m2-((a%m2)-b));
    int s = (modinv(t,m2)*d)%m2;
    return (a+s*m1+m1*m2)%(m1*m2);
}
signed main(){
    //cout<<f(1,2,2,3)<<endl;
    int N;
    cin>>N;
    vector<int> A(N),B(N),C(N),D(N);
    for(int i=0;i<N;i++){
        cin>>A[i]>>B[i];
        D[i] = A[i]-B[i];
    }
    {
        int s1 = 0, s2 = 0;
        for(int i=0;i<N;i++){
            s1 += modpow(2,i,mod1)*D[i]%mod1;
            s2 += modpow(2,i,mod2)*D[i]%mod2;
        }
        s1 %= mod1;
        s2 %= mod2;
        s1 = (s1*modinv(modpow(2,N,mod1)-1,mod1)%mod1)%mod1;
        s2 = (s2*modinv(modpow(2,N,mod2)-1,mod2)%mod2)%mod2;
        C[N-1] = f(s1,mod1,s2,mod2);

        int now = C[N-1];
        for(int i=0;i<N-1;i++){
            if((D[i]+now)%2 != 0){
                cout<<"No"<<endl;
                return 0;
            }
            C[i] = (D[i]+now)/2;
            now = C[i];
        }
        for(int i=0;i<N;i++)if(2*C[i]-C[(i+N-1)%N] != D[i] || C[i] < 0){
            cout<<"No"<<endl;
            return 0;
        }
    }
    set<pair<int,int>> s;
    for(int i=0;i<N;i++) s.insert({A[i],i});
    int ans = 0;
    while(true){
        pair<int,int> a = *s.rbegin();
        if(C[a.second] == 0) break;
        else if(a.first < 2){
            cout<<"No"<<endl;
            return 0;
        }
        int d = A[a.second]/2;
        bool p = false;
        if(d >= C[a.second]){
            d = C[a.second];
            p = true;
        }
        C[a.second] -= d;
        s.erase({A[a.second],a.second});
        s.erase({A[(a.second+1)%N],(a.second+1)%N});
        A[a.second] -= 2*d;
        A[(a.second+1)%N] += d;
        s.insert({A[a.second],a.second});
        s.insert({A[(a.second+1)%N],(a.second+1)%N});
    }
    int st = 0;
    for(int i=0;i<N;i++)if(C[i] == 0){
        st = i;
        break;
    }
    for(int i=st+1;i<st+N;i++){
        if(A[i%N] < 2*C[i%N]){
            cout<<"No"<<endl;
            return 0;
        }
        A[i%N] -= 2*C[i%N];
        A[(i+1)%N] += C[i%N];
    }
    cout<<"Yes"<<endl;
}

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