Submission #1045009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045009		urd05	Bring Down the Grading Server (CEOI23_gradingserver)	C++17	100 / 100	2231 ms	69916 KiB

gradingserver

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

long long s;
int q;
typedef pair<long long,long long> P;
typedef pair<long long,P> iP;
map<iP,long long> mp[2];

bool solve(long long a1,long long f1,long long a2,long long f2,int t=0) {
if (a2<=-f1*s) return true;
if (a1<=-f2*s) return false;
    if (a1>=s&&a2<s) {
        return true;
    }
    if (0<a1&&a1<s&&a2<=0) {
if (f2==0) {
return !solve(a2-a1,f2,a1,f1,1-t);
}
        return true;
    }
    if (a1<=0&&a2>=s) {
        return false;
    }
    if (a2>=s) {
        return !solve(a2-a1,f2,a1,f1,1-t);
    }
    if (a1<=0) {
        if (a2<=0) {
            long long tt=min((-a1)/s+1,(-a2)/s+1);
tt=min(tt,f1);
tt=min(tt,f2);
            return solve(a1+tt*s,f1-tt,a2+tt*s,f2-tt,t);
        }
if (f2==0) return false;
        if (f1==0) {
            long long b2=s-a2;
            long long cnt=(-a1)/(b2)+1;
            if (f2>=cnt) {
                return solve(a1+cnt*b2,f1,a2,f2-cnt,t);
            }
            else {
                return false;
            }
        }
        return !solve(a2,f2-1,a1+s,f1,1-t);
    }
assert(0<a1&&a1<s&&a2>0&&a2<s);
        if (f2==0) {
        return !solve(a2-a1,f2,a1,f1,1-t);
    }
    long long b2=s-a2;
    long long b1=s-a1;
    if (b2*f2>=b1) {
        return true;
    }
    if ((s-a1)*(f1+1)>=2*s-a2) {
        long long diff=(s-a1)*(f1+1)-2*s+a2;
        diff=diff/(b2*(f1+1))+1;
        diff=min(diff,f2);
            return solve(a1+b2*diff,f1,a2,f2-diff,t);
    }
    bool flag=false;
    if (f2>10*s||f1>10*s) {
        return true;
    }
    if (b2*max(f1,1LL)>=(10*s+1)/(f2*f2)) {
        return true;
    }
    if (mp[t].find(iP(f1,P(b2,f2)))!=mp[t].end()) {
        long long got=mp[t][iP(f1,P(b2,f2))];
        return a1+s*f2>=got;
    }
    long long lo=0;
    long long hi=1e12+7;
    if (solve(a2,f2-1,hi-s*f2+s,f1,1-t)&&solve(a2-hi+s*f2,f2,hi-s*f2,f1,1-t)) {
        mp[t][iP(f1,P(b2,f2))]=1e17+1;
        return false;
    }
    while (lo+1<hi) {
        long long mid=(lo+hi)/2;
        if (solve(a2,f2-1,mid-s*f2+s,f1,1-t)&&solve(a2-mid+s*f2,f2,mid-s*f2,f1,1-t)) {
            lo=mid;
        }
        else {
            hi=mid;
        }
    }
    mp[t][iP(f1,P(b2,f2))]=hi;
    return (a1+s*f2>=hi);
}

int main(void) {
    scanf("%lld %d",&s,&q);
    for(int i=0;i<q;i++) {
        long long c1,f1,c2,f2;
        scanf("%lld %lld %lld %lld",&c1,&f1,&c2,&f2);
        int got=solve(c1-s*f2,f1,c2-s*f1,f2);
        printf("%s\n",got?"YES":"NO");
    }
}

Compilation message (stderr)

gradingserver.cpp: In function 'bool solve(long long int, long long int, long long int, long long int, int)':
gradingserver.cpp:63:10: warning: unused variable 'flag' [-Wunused-variable]
   63 |     bool flag=false;
      |          ^~~~
gradingserver.cpp: In function 'int main()':
gradingserver.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf("%lld %d",&s,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
gradingserver.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         scanf("%lld %lld %lld %lld",&c1,&f1,&c2,&f2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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