Submission #135491

#TimeUsernameProblemLanguageResultExecution timeMemory
135491KLPPRemittance (JOI19_remittance)C++14
100 / 100
862 ms31832 KiB
#include<bits/stdc++.h> using namespace std; typedef long long int lld; #define rep(i,a,b) for(int i=a;i<b;i++) int number[2000000]; void add(int pos, lld x){ if(x==0)return; if(x>0){ number[pos]+=x%2; x/=2; if(number[pos]==2){ number[pos]=0; x++; } add(pos+1,x); }else{ number[pos]+=x%2; x/=2; if(number[pos]==-2){ number[pos]=0; x--; } add(pos+1,x); } } int main(){ int n; scanf("%d",&n); lld a[n]; lld b[n]; rep(i,0,n){ scanf("%lld %lld",&a[i],&b[i]); } bool eq=true; rep(i,0,n){ if(a[i]!=b[i])eq=false; } if(eq){ printf("Yes\n"); return 0; } /*eq=true; rep(i,0,n){ if(0!=b[i])eq=false; } if(eq){ printf("No\n"); return 0; }*/ rep(i,0,2000000)number[i]=0; rep(i,0,n){ add(i,a[i]-b[i]); } int last=-1; for(int i=1999999;i>-1;i--){ if(number[i]==1)last=i; if(number[i]==-1){ if(last==-1){ printf("No\n"); return 0; }else{ rep(j,i,last){ number[j]=1; } number[last]=0; last=i; } } } /*rep(i,0,10){ cout<<number[i]; }cout<<endl;*/ lld Pow[60]; Pow[0]=1; rep(i,1,59)Pow[i]=Pow[i-1]*2; lld c[n]; c[n-1]=0; for(int i=1999999;i>=n;i--){ while(number[i]==1){ int m=i-n; number[m]++; number[i]--; c[n-1]+=Pow[i-n]; while(number[m]==2){ number[m]=0; number[m+1]++; m++; } } } //rep(i,0,10)cout<<number[i]<<endl; //cout<<c[n-1]<<endl; int num=number[0]; rep(i,0,n){ if(number[i]!=num){ printf("No\n"); return 0; } } c[n-1]+=num; //cout<<c[n-1]<<endl; for(int i=n-2;i>-1;i--){ c[i]=c[i+1]*2+b[i+1]-a[i+1]; } rep(i,0,n){ if(c[i]<0){ printf("No\n"); return 0; } } rep(turn,0,60){ rep(i,0,n){ lld C=min(c[i],a[i]/2); c[i]-=C; a[i]-=2*C; a[(i+1)%n]+=C; } } rep(i,0,n){ if(a[i]!=b[i]){ printf("No\n"); return 0; } } printf("Yes\n"); return 0; }

Compilation message (stderr)

remittance.cpp: In function 'int main()':
remittance.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
remittance.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&a[i],&b[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...