Submission #409539

#	Time	Username	Problem	Language	Result	Execution time	Memory
409539		cpp219	Remittance (JOI19_remittance)	C++14	0 / 100	1 ms	332 KiB

remittance

#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e6 + 9;
const ll Log2 = 20;
//const ll mod = 2038074743;
const ll mod = 1e9 + 7;
typedef pair<ll,ll> LL;

ll n,a[N],b[N],send[N];

void Badgame(){
    cout<<"No"; exit(0);
}

void Goodgame(){
    cout<<"Yes"; exit(0);
}

ll bpow(ll a,ll b){
    if (!b) return 1;
    ll t = bpow(a,b/2); t = (t * t)%mod;
    if (b & 1) return (t * a)% mod;
    return t;
}

ll Rev(ll x){
    //cout<<bpow(x,mod - 2); exit(0);
    return bpow(x,mod - 2);
}

ll Divide(ll x,ll y){
    return (x * Rev(y))%mod;
}
ll mx,bit[N],mx1;

bool chkbit(){
    ll now = 0,last = 0;
    for (ll i = 0;i <= n;i++){
        now += bit[i];
        if (i == n) break;
        if (i % 2 != 0) last = (now > 0);
        now /= 2;
    }
    return (now > 0 || (!now && last));
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "tst"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n;
    for (ll i = 1;i <= n;i++) cin>>a[i]>>b[i],mx = max(mx,b[i]),mx1 = max(mx1,a[i]);
    ll sum = 0; bit[0]++;
    for (ll i = 1;i <= n;i++){
        sum += (bpow(2,i - 1)*(a[i] - b[i]))%mod,sum %= mod;
        bit[i - 1] += a[i] - b[i];
    }
    bit[n] = -1;
    if (!chkbit() && sum != 0) Badgame();
    send[0] = send[n] = Divide(sum,(bpow(2,n) - 1));
    //cout<<Rev(31); return 0;
    //cout<<sum<<" "<<bpow(2,n) - 1<<" "<<send[n]; return 0;
    if (send[n] < 0) Badgame();
    for (ll i = 1;i < n;i++){
        send[i] = a[i] - b[i] + send[i - 1];
        if (send[i] % 2 || send[i] < 0) Badgame();
        send[i] /= 2;
    }
    if (mx || (!mx && !mx1)) Goodgame();
    else Badgame();
}

Compilation message (stderr)

remittance.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
remittance.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
remittance.cpp: In function 'int main()':
remittance.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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