Submission #1059105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059105		byunjaewoo	Bring Down the Grading Server (CEOI23_gradingserver)	C++17	100 / 100	2919 ms	124424 KiB

gradingserver

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

int S, Q;
map<pair<int, pair<int, int>>, int> X[2];
map<pair<int, pair<int, int>>, bool> chk[2];

bool F(int a1, int f1, int a2, int f2, int p) {
    if(a2<=-f1*S) return true;
    if(a1<=-f2*S) return false;
    int c1=a1+f2*S, c2=a2+f1*S, b1=S-a1, b2=S-a2;
    if(a1>=S && a2<S) return true;
    if(a1<=0 && a2>=S) return false;
    if(a1>0 && a2>=S) return !F(a2-a1, f2, a1, f1, 1-p);
    if(a1<=0 && a2<=0) {
        int tmp=min({f1, f2, (-a1)/S+1, (-a2)/S+1});
        return F(a1+S*tmp, f1-tmp, a2+S*tmp, f2-tmp, p);
    }
    if(a1<=0 && 0<a2 && a2<S) {
        if(!f2) return false;
        if(!f1) {
            int tmp=(-a1)/b2+1;
            if(f2>=tmp) return F(a1+tmp*b2, f1, a2, f2-tmp, p);
            return false;
        }
        return !F(a2, f2-1, a1+S, f1, 1-p);
    }
    if(0<a1 && a1<S && a2<=0) {
        if(!f2) return !F(a2-a1, f2, a1, f1, 1-p);
        return true;
    }
    if(!f2) return !F(a2-a1, f2, a1, f1, 1-p);
    if(b2*f2>=b1) return true;
    if(a2-a1+b1*f1>=S) {
        int tmp=min(f2, (b1*f1-a1+a2-S)/(b2*(f1+1))+1);
        return F(a1+b2*tmp,f1,a2,f2-tmp,p);
    }
    if(f1>=8*S || f2>=8*S) return true;
    if(b2*max(1ll, f1)*f2>=(8*S)/f2) return true;
    if(chk[p][{f1, {b2, f2}}]) return c1>=X[p][{f1, {b2, f2}}];
    chk[p][{f1, {b2, f2}}]=true;
    int tmp=1e17;
    for(int s=0, e=1e12; s<=e; ) {
        int _c1=(s+e)/2;
        if(F(a2, f2-1, (_c1-S*f2)+S, f1, 1-p) && F(a2-(_c1-S*f2), f2, (_c1-S*f2), f1, 1-p)) s=_c1+1;
        else tmp=_c1, e=_c1-1;
    }
    X[p][{f1, {b2, f2}}]=tmp;
    return c1>=tmp;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>S>>Q;
    while(Q--) {
        int c1, f1, c2, f2; cin>>c1>>f1>>c2>>f2;
        if(F(c1-f2*S, f1, c2-f1*S, f2, 0)) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

Compilation message (stderr)

gradingserver.cpp: In function 'bool F(long long int, long long int, long long int, long long int, long long int)':
gradingserver.cpp:12:21: warning: unused variable 'c2' [-Wunused-variable]
   12 |     int c1=a1+f2*S, c2=a2+f1*S, b1=S-a1, b2=S-a2;
      |                     ^~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 5: 25 / 25
• Subtask 4: 20 / 20
• Subtask 6: 20 / 20
• Subtask 7: 15 / 15