Submission #1331977

#TimeUsernameProblemLanguageResultExecution timeMemory
1331977boclobanchatRemittance (JOI19_remittance)C++20
55 / 100
15 ms1980 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+67;
long long a[MAXN],b[MAXN],A[MAXN],B[MAXN],C[MAXN],cnt[MAXN],F[MAXN];
long long ctwist(int idx,int n)
{
	int m=0;
	for(int i=idx;i<idx+n;i++) m++,A[m]=a[(i-1)%n+1],B[m]=b[(i-1)%n+1];
	for(int i=1;i<=n+36;i++)
	{
		C[i]+=A[i]-B[i];
		if(C[i]<0) C[i+1]-=(-C[i]+1)/2,C[i]+=(-C[i]+1)/2*2;
		C[i+1]+=C[i]/2,C[i]%=2;
	}
	if(C[n+37]<0)
	{
		cout<<"No";
		exit(0);
	}
	long long sum=0;
	for(int a=1;a<=30;a++) if(C[a])
	{
		sum+=(1LL<<(a-1));
		for(int i=a;i<=n+36;i++)
		{
			if(i<a+n) C[i]--;
			if(C[i]<0) C[i+1]-=(-C[i]+1)/2,C[i]+=(-C[i]+1)/2*2;
			C[i+1]+=C[i]/2,C[i]%=2;
		}
	}
	bool cc=true;
	for(int i=1;i<=n+37;i++) cc&=(!C[i]);
	if(!cc)
	{
		cout<<"No";
		exit(0);
	}
	return sum;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
	for(int i=1;i<=n;i++) F[i]=ctwist(i,n);
	for(int t=1;t<=36;t++) for(int i=1;i<=n;i++)
	{
		long long k=min(F[i],a[(i-2+n)%n+1]/2);
		F[i]-=k,a[i]+=k,a[(i-2+n)%n+1]-=k*2;
	}
	for(int i=1;i<=n;i++) if(a[i]!=b[i]) return cout<<"No",0;
	cout<<"Yes";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...