oj.uz

Submission #1058946

# Submission time Handle Problem Language Result Execution time Memory
1058946 2024-08-14T15:14:59 Z byunjaewoo Bring Down the Grading Server (CEOI23_gradingserver) C++17
10 / 100
 71 ms 1252 KB 
#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)/(b2*(f1+1))+1);
        return F(a1+b2*tmp,f1,a2,f2-tmp,p);
    }
    if(f1>=11*S || f2>=11*S) return true;
    if(b2*max(1ll, f1)*f2>=(11*S)/f2) return true;
    if(chk[p][{f1, {b1, f2}}]) return c1>=X[p][{f1, {b1, f2}}];
    chk[p][{f1, {b1, f2}}]=true;
    int tmp=1e17;
    for(int s=0, e=2e12; 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, {b1, f2}}]=tmp;
    cout<<tmp<<"\n";
    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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 37 ms 1204 KB Output is correct
3 Incorrect 38 ms 1104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 37 ms 1204 KB Output is correct
3 Incorrect 38 ms 1104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 1104 KB Output is correct
2 Correct 65 ms 1252 KB Output is correct
3 Correct 68 ms 1212 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 37 ms 1204 KB Output is correct
3 Incorrect 38 ms 1104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 37 ms 1204 KB Output is correct
3 Incorrect 38 ms 1104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 37 ms 1204 KB Output is correct
3 Incorrect 38 ms 1104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 37 ms 1204 KB Output is correct
3 Incorrect 38 ms 1104 KB Output isn't correct
4 Halted 0 ms 0 KB -