#include <bits/stdc++.h>
using namespace std;
#define int long long
const int modulo = 1e9+7;
int A[100001];
int B[100001];
int curr[100001];
int arr[100001];
int inv(int a){
int p = modulo-2;
int ans = 1;
while(p){
if(p&1){
ans*=a;
ans%=modulo;
p--;
}
a*=a;
a%=modulo;
p/=2;
}
return ans;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for(int i=0;i<n;i++)cin>>A[i]>>B[i];
int start = 0;
int power = 1;
for(int i=1;i<n;i++){
start=(start+modulo+((power*(A[i]-B[i]))%modulo))%modulo;
power*=2ll;
power%=modulo;
start%=modulo;
}
start=(start+modulo+((power*(A[0]-B[0]))%modulo))%modulo;
power*=2ll;
power%=modulo;
start%=modulo;
power+=modulo-1;
power%=modulo;
start=(start*inv(power))%modulo;
arr[0]=start;
bool works = true;
if(start<0)works=false;
for(int x=1;x<n;x++){
arr[x]=arr[x-1]+A[x]-B[x];
if(arr[x]<0)works=false;
if(arr[x]&1)works=false;
arr[x]/=2;
}
int backup = arr[n-1]+A[0]-B[0];
if(backup&1)works=false;
if(arr[0]!=backup/2)works=false;
if(!works)goto shit;
for(int x=0;x<n;x++)curr[x]=A[x];
for(int rounds=1;rounds<40;rounds++){
for(int x=0;x<n;x++){
int uses = min(arr[x],curr[x]/2);
curr[x]-=2*uses;
arr[x]-=uses;
curr[(x+1)%n]+=uses;
}
}
for(int x=0;x<n;x++)if(curr[x]!=B[x])works=false;
if(works){
cout << "Yes\n";
return 0;
}
shit:
cout << "No\n";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2648 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2424 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2508 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 25 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 27 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 30 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 31 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2648 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2424 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2508 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 25 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 27 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 30 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 31 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 33 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 34 |
Correct |
1 ms |
2512 KB |
Output is correct |
| 35 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 36 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 37 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 38 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 39 |
Correct |
1 ms |
2592 KB |
Output is correct |
| 40 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 41 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 42 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 43 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 44 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 45 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 46 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 47 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 48 |
Correct |
1 ms |
2508 KB |
Output is correct |
| 49 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 50 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 51 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 52 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 53 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 54 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 55 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 56 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 57 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 58 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 59 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 60 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 61 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 62 |
Correct |
0 ms |
2396 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2648 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2424 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2508 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 25 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 27 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 30 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 31 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 33 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 34 |
Correct |
1 ms |
2512 KB |
Output is correct |
| 35 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 36 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 37 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 38 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 39 |
Correct |
1 ms |
2592 KB |
Output is correct |
| 40 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 41 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 42 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 43 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 44 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 45 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 46 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 47 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 48 |
Correct |
1 ms |
2508 KB |
Output is correct |
| 49 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 50 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 51 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 52 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 53 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 54 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 55 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 56 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 57 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 58 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 59 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 60 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 61 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 62 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 63 |
Runtime error |
20 ms |
8100 KB |
Execution killed with signal 11 |
| 64 |
Halted |
0 ms |
0 KB |
- |
