oj.uz

Submission #1058473

# Submission time Handle Problem Language Result Execution time Memory
1058473 2024-08-14T10:10:48 Z byunjaewoo Bring Down the Grading Server (CEOI23_gradingserver) C++17
10 / 100
 70 ms 1216 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) {
    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(b2*max(1ll, f1)>=(11*S)/f2/f2) return true;
    if(chk[p][{f1, {b1, f2}}]) return c1>=X[p][{f1, {b1, f2}}];
    chk[p][{f1, {b1, f2}}]=true;
    int tmp=0;
    X[p][{f1, {b1, f2}}]=2e12;
    for(int s=1, 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;
    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:10:21: warning: unused variable 'c2' [-Wunused-variable]
   10 |     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 0 ms 348 KB Output is correct
2 Correct 0 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 348 KB Output is correct
2 Correct 37 ms 1172 KB Output is correct
3 Incorrect 40 ms 1112 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 348 KB Output is correct
2 Correct 37 ms 1172 KB Output is correct
3 Incorrect 40 ms 1112 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 70 ms 1216 KB Output is correct
2 Correct 66 ms 1100 KB Output is correct
3 Correct 68 ms 1108 KB Output is correct
4 Correct 1 ms 344 KB Output is correct

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 37 ms 1172 KB Output is correct
3 Incorrect 40 ms 1112 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 348 KB Output is correct
2 Correct 37 ms 1172 KB Output is correct
3 Incorrect 40 ms 1112 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 348 KB Output is correct
2 Correct 37 ms 1172 KB Output is correct
3 Incorrect 40 ms 1112 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 348 KB Output is correct
2 Correct 37 ms 1172 KB Output is correct
3 Incorrect 40 ms 1112 KB Output isn't correct
4 Halted 0 ms 0 KB -