Submission #134503

#	Time	Username	Problem	Language	Result	Execution time	Memory
134503		RezwanArefin01	Remittance (JOI19_remittance)	C++17	100 / 100	975 ms	23912 KiB

remittance

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 1e6 + 10; 
const int mod = 1e9 + 7;
ll a[N], b[N], f[N];  
int n;

inline int Pow(int a, int p) {
    int ret = 1; while(p) {
        if(p & 1) ret = (ll) ret * a % mod;
        a = (ll) a * a % mod;
        p >>= 1;
    } return ret;
}

int main(int argc, char const *argv[]) {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    scanf("%d", &n);

    ll pw = 1, I = 0; 
    for(int i = 0; i < n; ++i) {
        scanf("%d %d", &a[i], &b[i]); 
        I += pw * (a[i] - b[i] + mod) % mod;
        if(I >= mod) I -= mod;
        pw = pw * 2 % mod;
    }

    I *= Pow(pw - 1, mod - 2); 
    I %= mod;

    f[n] = I;
    
    auto no = []() { puts("No"); exit(0); };

    for(int k = 70; k--; ) {
        int idx = 0; 
        for(int i = n - 1; i > 0; --i) {
            f[i] = 2 * f[i + 1] - a[i];
            if(f[i] <= 0) { idx = i; break; }
        }   

        for(int i = idx; i < n - 1; ++i) {
            ll x = min(a[i] / 2, f[i + 1]);
            a[i] -= 2 * x; 
            a[(i + 1) % n] += x;
        }

        ll x = min(a[n - 1] / 2, f[n]); 
        a[n - 1] -= 2 * x;
        f[n] -= x; 
        a[0] += x;

        if(idx) break; 
    }

    for(int i = 0; i < n; ++i) {
        int x = a[i] - b[i];
        if(x < 0 || (x & 1)) no();
        a[i] -= x; 
        a[(i + 1) % n] += x / 2;
    }

    for(int i = 0; i < n; ++i) {
        if(a[i] != b[i]) no(); 
    }

    puts("Yes"); 
}

Compilation message (stderr)

remittance.cpp: In function 'int main(int, const char**)':
remittance.cpp:28:36: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
         scanf("%d %d", &a[i], &b[i]); 
                        ~~~~~       ^
remittance.cpp:28:36: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll* {aka long long int*}' [-Wformat=]
remittance.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
remittance.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a[i], &b[i]); 
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45