제출 #1145548

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145548		keisuke6	송금 (JOI19_remittance)	C++20	100 / 100	807 ms	31740 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 sc = 0;
    for(int x:C) sc += x;
    for(int t=0;t<100000000000;t++){
        for(int i=0;i<N;i++){
            if(C[(i+N-1)%N] == 0 && A[i] < 2*C[i]){
                cout<<"No"<<endl;
                return 0;
            }
            int d = min(C[i],A[i]/2);
            A[i] -= 2*d;
            C[i] -= d;
            A[(i+1)%N] += d;
            sc -= d;
            if(!sc){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
        if(clock() > CLOCKS_PER_SEC*0.8){
            cout<<"No"<<endl;
            return 0;
        }
    }
}

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