Submission #339434

#	Time	Username	Problem	Language	Result	Execution time	Memory
339434		sealnot123	Remittance (JOI19_remittance)	C++14	100 / 100	935 ms	60176 KiB

remittance

/*
	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;
    }
    // check correctness
    FOR(i, 0, n-1){
        if(x[i]-2*x[(i+1)%n] != rem[i]){
            return false;
        }
    }
    // ok
    FOR(i, 0, n-1){
        if(B[i] != 0){
            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;
    }
    bool eq = true;
    FOR(i, 0, n-1){
        if(A[i] != B[i]){
            eq = false; break;
        }
    }
    if(eq){
        puts("Yes"); return;
    }
    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: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45