oj.uz

Submission #339380

# Submission time Handle Problem Language Result Execution time Memory
339380 2020-12-25T07:05:19 Z sealnot123 Remittance (JOI19_remittance) C++14
0 / 100
 1 ms 384 KB 
/*
	Author: AquaBlaze
    Keqing best girl :)
    Nephren will always be in my heart
*/
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define ROF(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())
#define pc(x) putchar(x)
#define MP make_pair
#define MT make_tuple

using namespace std;

typedef long long i64;
typedef tuple<int,int,int> iii;
typedef pair<int,int> pii;
typedef pair<long,long> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int N = 1000003, lg = 30;
const int mod = 1000000007;
int n;
i64 rem[N];
i64 x[N];

i64 pw(i64 a, i64 b){
    i64 ans = 1, res = a;
    for(i64 i = 1; i <= b; i<<=1, res=res*res%mod){
        if(i&b) ans = ans*res%mod;
    }
    return ans;
}

i64 A[N], B[N];

void solve(){
    cin >> n;
    FOR(i, 0, n-1){
        i64 a, b;
        cin >> a >> b;
        A[i] = a;
        B[i] = b;
        rem[i] = b-a;
    }
    i64 p2 = 1;
    FOR(i, 0, n-1){
        x[0] = (x[0]+rem[i]*p2)%mod;
        p2 = p2*2%mod;
    }
    if(x[0]<0) x[0]+=mod;
    p2 = (1-p2)%mod+mod;
    p2 = pw(p2, mod-2);
    x[0] = x[0]*p2%mod;
    //printf("%lld\n",x[0]);
    FOR(i, 1, n-1){
        x[i] = x[i-1]-rem[i-1];
        //printf("%lld\n",x[i]);
        if(x[i] < 0 || x[i]%2!=0){
            puts("No"); return;
        }
        x[i] /= 2;
    }
    FOR(i, 0, n-1){
        if(-rem[i] >= x[(i+1)%n]){
            // this is the start
            int st = i;
            A[i] -= 2*x[(i+1)%n];
            A[(i+1)%n] += x[(i+1)%n];
            for(int j = (i+1)%n; j != st; j=(j+1)%n){
                if(x[(j+1)%n] > 0){
                    if(A[j] < 2*x[(j+1)%n]){
                        // lmao bye
                        puts("No"); return ;
                    }
                    A[j] -= 2*x[(j+1)%n];
                    A[(j+1)%n] += x[(j+1)%n];
                }
            }
            FOR(j, 0, n-1){
                if(A[j] != B[j]){
                    puts("No"); return ;
                }
            }
            puts("Yes"); return;
        }
    }
    puts("No");
}

int main(){
    solve();
	return 0;
}
/*
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

Subtask #1
0 / 15.0

# Verdict Execution time Memory 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 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 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 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Incorrect 1 ms 364 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory 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 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 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 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Incorrect 1 ms 364 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory 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 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 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 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Incorrect 1 ms 364 KB Output isn't correct
21 Halted 0 ms 0 KB -