oj.uz

답안 #339387

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
339387 2020-12-25T07:18:49 Z sealnot123 송금 (JOI19_remittance) C++14
0 / 100
 7 ms 8192 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;
int mod3 = 1000000021;
int mod2 = 1000000009;
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];
i64 tA[N], tB[N];

bool check(){
    memset(x, 0, sizeof x);
    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 %= 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){
            return false;
        }
        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
                        return false;
                    }
                    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]){
                    return false;
                }
            }
            return true;
        }
    }
    return false;
}

void solve(){
    cin >> n;
    FOR(i, 0, n-1){
        i64 a, b;
        cin >> a >> b;
        tA[i] = A[i] = a;
        tB[i] = B[i] = b;
        rem[i] = b-a;
    }
    if(check()){
        puts("Yes"); return;
    }
    FOR(i, 0, n-1) A[i] = tA[i], B[i] = tB[i];
    mod = mod2;
    if(check()){
        puts("Yes"); return;
    }
    FOR(i, 0, n-1) A[i] = tA[i], B[i] = tB[i];
    mod = mod3;
    if(check()){
        puts("Yes"); return;
    }
    puts("No");
}

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

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8172 KB Output is correct
2 Correct 5 ms 8172 KB Output is correct
3 Correct 5 ms 8172 KB Output is correct
4 Correct 5 ms 8172 KB Output is correct
5 Correct 5 ms 8172 KB Output is correct
6 Correct 5 ms 8172 KB Output is correct
7 Correct 5 ms 8172 KB Output is correct
8 Correct 5 ms 8172 KB Output is correct
9 Correct 5 ms 8172 KB Output is correct
10 Correct 5 ms 8172 KB Output is correct
11 Correct 5 ms 8172 KB Output is correct
12 Correct 6 ms 8192 KB Output is correct
13 Correct 7 ms 8172 KB Output is correct
14 Correct 6 ms 8172 KB Output is correct
15 Correct 7 ms 8172 KB Output is correct
16 Correct 7 ms 8172 KB Output is correct
17 Correct 6 ms 8172 KB Output is correct
18 Correct 5 ms 8172 KB Output is correct
19 Correct 7 ms 8192 KB Output is correct
20 Incorrect 5 ms 8172 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8172 KB Output is correct
2 Correct 5 ms 8172 KB Output is correct
3 Correct 5 ms 8172 KB Output is correct
4 Correct 5 ms 8172 KB Output is correct
5 Correct 5 ms 8172 KB Output is correct
6 Correct 5 ms 8172 KB Output is correct
7 Correct 5 ms 8172 KB Output is correct
8 Correct 5 ms 8172 KB Output is correct
9 Correct 5 ms 8172 KB Output is correct
10 Correct 5 ms 8172 KB Output is correct
11 Correct 5 ms 8172 KB Output is correct
12 Correct 6 ms 8192 KB Output is correct
13 Correct 7 ms 8172 KB Output is correct
14 Correct 6 ms 8172 KB Output is correct
15 Correct 7 ms 8172 KB Output is correct
16 Correct 7 ms 8172 KB Output is correct
17 Correct 6 ms 8172 KB Output is correct
18 Correct 5 ms 8172 KB Output is correct
19 Correct 7 ms 8192 KB Output is correct
20 Incorrect 5 ms 8172 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8172 KB Output is correct
2 Correct 5 ms 8172 KB Output is correct
3 Correct 5 ms 8172 KB Output is correct
4 Correct 5 ms 8172 KB Output is correct
5 Correct 5 ms 8172 KB Output is correct
6 Correct 5 ms 8172 KB Output is correct
7 Correct 5 ms 8172 KB Output is correct
8 Correct 5 ms 8172 KB Output is correct
9 Correct 5 ms 8172 KB Output is correct
10 Correct 5 ms 8172 KB Output is correct
11 Correct 5 ms 8172 KB Output is correct
12 Correct 6 ms 8192 KB Output is correct
13 Correct 7 ms 8172 KB Output is correct
14 Correct 6 ms 8172 KB Output is correct
15 Correct 7 ms 8172 KB Output is correct
16 Correct 7 ms 8172 KB Output is correct
17 Correct 6 ms 8172 KB Output is correct
18 Correct 5 ms 8172 KB Output is correct
19 Correct 7 ms 8192 KB Output is correct
20 Incorrect 5 ms 8172 KB Output isn't correct
21 Halted 0 ms 0 KB -