oj.uz

Submission #135489

# Submission time Handle Problem Language Result Execution time Memory
135489 2019-07-24T06:44:03 Z KLPP Remittance (JOI19_remittance) C++14
0 / 100
 12 ms 8184 KB 
#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++;
      }
    }
  }
  c[n-1]++;
  //rep(i,0,10)cout<<number[i]<<endl;
  //cout<<c[n-1]<<endl;
  rep(i,0,n){
    if(number[i]!=1){
      printf("No\n");
      return 0;
    }
  }
  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

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]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8184 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 12 ms 8184 KB Output is correct
5 Correct 12 ms 8184 KB Output is correct
6 Incorrect 12 ms 8184 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8184 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 12 ms 8184 KB Output is correct
5 Correct 12 ms 8184 KB Output is correct
6 Incorrect 12 ms 8184 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8184 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 12 ms 8184 KB Output is correct
5 Correct 12 ms 8184 KB Output is correct
6 Incorrect 12 ms 8184 KB Output isn't correct
7 Halted 0 ms 0 KB -