This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |