Submission #265597

#	Time	Username	Problem	Language	Result	Execution time	Memory
265597		easrui	Remittance (JOI19_remittance)	C++14	100 / 100	497 ms	31736 KiB

remittance

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN = 1e6+35;
const int MOD = 1e9+7;

ll A[MN],B[MN],C[MN],F[MN],k[30];

void impos()
{
	cout << "No";
	exit(0);
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);

    int N;
    cin >> N;

    for(int i=0; i<N; i++) cin >> A[i] >> B[i];

    k[0] = 1;
    for(int i=1; i<30; i++){
    	k[i] = k[i-1]*2;
    }

    for(int i=N-1; i>=0; i--){
	    for(int j=0; j<30; j++){
	    	if(abs(A[i]-B[i])&k[j]){
	    		if(A[i]>B[i]) F[i+j+1]++;
	    		else F[i+j+1]--;
	    	}
	    }
    }


    for(int i=0; i<N+29; i++){
    	if(F[i]>=0){
    		F[i+1] += F[i]/2;
    		F[i]%=2;
    	}
    	else{
    		F[i+1] -= (1-F[i])/2;
    		F[i]=(-F[i])%2;
    	}
    }
    if(F[N+29]<0) impos();

    for(int i=N+29; i>=N; i--){
    	F[i-N] += F[i];
    	C[N-1] += F[i]*k[i-N];
    	F[i] = 0;
    }

    for(int t=0; t<5; t++){
	    for(int i=0; i<N; i++){
	    	F[i+1] += F[i]/2;
	    	F[i]%=2;
	    }
	    F[0] += F[N];
	    C[N-1] += F[N];
	    F[N] = 0;
	}

	F[0]++;
    for(int i=0; i<N; i++){
    	F[i+1] += F[i]/2;
    	F[i]%=2;
    }	

    ll sum = 0;
	for(int i=0; i<=N; i++){
		sum += F[i];
	}

	if(F[N]) C[N-1]++;
	if(sum!=1) impos();
	if(!F[0]&&!F[N]) impos();
    if(C[N-1]%2) impos();


    for(int i=0; i<N-1; i++){
    	C[i] = A[i]-B[i]+C[(i+N-1)%N]/2;
    	if(C[i]<0||C[i]%2) impos();
    }

    for(int t=0; t<3; t++){
	    for(int i=0; i<N; i++){
	    	ll x = min(C[i]/2,A[i]/2)*2;
	    	A[i] -= x;
	    	A[(i+1)%N] += x/2;
	    	C[i] -= x;
	    }
    }

    for(int i=0; i<N; i++) if(A[i]!=B[i]) impos();
    cout << "Yes";

}

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