#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define M 1000001
typedef long long ll;
const int p=53;
const long long MOD=1000000007;
using namespace std;
ll a[M],b[M],c[M],d[M],n;
ll pow2[M];
ll power(ll a,ll b){
ll res=1;
while(b>0){
if(b&1){
res=res*a;
if(res>=MOD) res%=MOD;
}
b>>=1;
a=a*a;
if(a>=MOD) a%=MOD;
}
return res;
}
ll turn(ll k){
return (k+10*MOD)%MOD;
}
ll suma,sumb,sumgiven;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
pow2[0]=1;
for(int i=1;i<=n;i++){
pow2[i]=pow2[i-1]*2;
if(pow2[i]>=MOD) pow2[i]%=MOD;
}
for(int i=0;i<n;i++){
cin >> a[i] >> b[i];
suma+=a[i];
sumb+=b[i];
c[i]=a[i]-b[i];
}
long long res=0;
for(int i=1;i<n;i++){
res+=((turn(c[i])*pow2[i-1])%MOD);
if(res>=MOD) res%=MOD;
}
bool f=0;
res+=((c[0]*pow2[n-1])%MOD);
if(res>=MOD) res%=MOD;
res=res*power(pow2[n]-1,MOD-2);
if(res>=MOD) res%=MOD;
d[0]=res;
sumgiven=d[0];
for(int i=1;i<n;i++){
ll e=c[i]+d[i-1];
if(e&1){
cout << "No";
return 0;
}
d[i]=e/2;
sumgiven+=(d[i]);
if(d[i]<0){
cout << "No";
return 0;
}
if(d[i-1]+a[i]<2*d[i]){
cout << "No";
return 0;
}
if(a[i]>=2*d[i]) f=1;
}
if(d[n-1]+a[0]<2*d[0]){
cout << "No";
return 0;
}
if(c[0]-2*d[0]+d[n-1]!=0){
cout << "No";
return 0;
}
if(sumgiven+sumb!=suma){
cout << "No";
return 0;
}
int last=-1,i=0,p=0;
bool flag=0;
while(1){
ll e=a[i]/2;
ll k=min(e,d[i]);
if(k==0){
if(last==i){
cout << "No";
return 0;
}
}
if(d[i]==0){
p++;
}
else p=0;
a[i]-=(2*k);
if(i==n-1){
a[0]+=k;
}
else a[i+1]+=k;
d[i]-=k;
if(d[i]>0) flag=1;
if(i==n-1) i=0;
else i++;
if(p==n){
cout << "Yes";
return 0;
}
}
}
Compilation message
remittance.cpp: In function 'int main()':
remittance.cpp:50:7: warning: variable 'f' set but not used [-Wunused-but-set-variable]
50 | bool f=0;
| ^
remittance.cpp:88:7: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
88 | bool flag=0;
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
0 ms |
364 KB |
Output is correct |
| 9 |
Correct |
0 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
0 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
1 ms |
364 KB |
Output is correct |
| 17 |
Correct |
1 ms |
364 KB |
Output is correct |
| 18 |
Correct |
0 ms |
364 KB |
Output is correct |
| 19 |
Correct |
1 ms |
364 KB |
Output is correct |
| 20 |
Execution timed out |
1093 ms |
364 KB |
Time limit exceeded |
| 21 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
0 ms |
364 KB |
Output is correct |
| 9 |
Correct |
0 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
0 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
1 ms |
364 KB |
Output is correct |
| 17 |
Correct |
1 ms |
364 KB |
Output is correct |
| 18 |
Correct |
0 ms |
364 KB |
Output is correct |
| 19 |
Correct |
1 ms |
364 KB |
Output is correct |
| 20 |
Execution timed out |
1093 ms |
364 KB |
Time limit exceeded |
| 21 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
0 ms |
364 KB |
Output is correct |
| 9 |
Correct |
0 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
0 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
1 ms |
364 KB |
Output is correct |
| 17 |
Correct |
1 ms |
364 KB |
Output is correct |
| 18 |
Correct |
0 ms |
364 KB |
Output is correct |
| 19 |
Correct |
1 ms |
364 KB |
Output is correct |
| 20 |
Execution timed out |
1093 ms |
364 KB |
Time limit exceeded |
| 21 |
Halted |
0 ms |
0 KB |
- |
