Submission #1145544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145544		keisuke6	Remittance (JOI19_remittance)	C++20	0 / 100	0 ms	396 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;
        }
    }
    int ans = 0;
    int st = -1;
    for(int i=0;i<N;i++)if(A[i] >= 2*C[i]){
        A[i] -= 2*C[i];
        A[(i+1)%N] += C[i];
        C[i] = 0;
        st = i;
        break;
    }
    if(st == -1){
        cout<<"No"<<endl;
        return 0;
    }
    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: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 45