oj.uz

Submission #1059100

# Submission time Handle Problem Language Result Execution time Memory
1059100 2024-08-14T17:12:57 Z byunjaewoo Bring Down the Grading Server (CEOI23_gradingserver) C++17
15 / 100
 4000 ms 4692 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-S)/(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=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, {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: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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 43 ms 1128 KB Output is correct
3 Correct 69 ms 1112 KB Output is correct
4 Correct 117 ms 3920 KB Output is correct
5 Correct 40 ms 3920 KB Output is correct
6 Correct 96 ms 3924 KB Output is correct
7 Correct 145 ms 3920 KB Output is correct
8 Correct 137 ms 3920 KB Output is correct
9 Correct 45 ms 3984 KB Output is correct

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 43 ms 1128 KB Output is correct
3 Correct 69 ms 1112 KB Output is correct
4 Correct 117 ms 3920 KB Output is correct
5 Correct 40 ms 3920 KB Output is correct
6 Correct 96 ms 3924 KB Output is correct
7 Correct 145 ms 3920 KB Output is correct
8 Correct 137 ms 3920 KB Output is correct
9 Correct 45 ms 3984 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 38 ms 3920 KB Output is correct
12 Correct 66 ms 4060 KB Output is correct
13 Correct 88 ms 4124 KB Output is correct
14 Correct 39 ms 3896 KB Output is correct
15 Correct 92 ms 3920 KB Output is correct
16 Correct 141 ms 3880 KB Output is correct
17 Correct 137 ms 3924 KB Output is correct
18 Correct 37 ms 3928 KB Output is correct
19 Correct 42 ms 4692 KB Output is correct
20 Correct 78 ms 4436 KB Output is correct
21 Execution timed out 4014 ms 3156 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 1180 KB Output is correct
2 Correct 77 ms 1216 KB Output is correct
3 Correct 68 ms 1104 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 348 KB Output is correct
2 Correct 43 ms 1128 KB Output is correct
3 Correct 69 ms 1112 KB Output is correct
4 Correct 117 ms 3920 KB Output is correct
5 Correct 40 ms 3920 KB Output is correct
6 Correct 96 ms 3924 KB Output is correct
7 Correct 145 ms 3920 KB Output is correct
8 Correct 137 ms 3920 KB Output is correct
9 Correct 45 ms 3984 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 38 ms 3920 KB Output is correct
12 Correct 66 ms 4060 KB Output is correct
13 Correct 88 ms 4124 KB Output is correct
14 Correct 39 ms 3896 KB Output is correct
15 Correct 92 ms 3920 KB Output is correct
16 Correct 141 ms 3880 KB Output is correct
17 Correct 137 ms 3924 KB Output is correct
18 Correct 37 ms 3928 KB Output is correct
19 Correct 42 ms 4692 KB Output is correct
20 Correct 78 ms 4436 KB Output is correct
21 Execution timed out 4014 ms 3156 KB Time limit exceeded
22 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 43 ms 1128 KB Output is correct
3 Correct 69 ms 1112 KB Output is correct
4 Correct 117 ms 3920 KB Output is correct
5 Correct 40 ms 3920 KB Output is correct
6 Correct 96 ms 3924 KB Output is correct
7 Correct 145 ms 3920 KB Output is correct
8 Correct 137 ms 3920 KB Output is correct
9 Correct 45 ms 3984 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 38 ms 3920 KB Output is correct
12 Correct 66 ms 4060 KB Output is correct
13 Correct 88 ms 4124 KB Output is correct
14 Correct 39 ms 3896 KB Output is correct
15 Correct 92 ms 3920 KB Output is correct
16 Correct 141 ms 3880 KB Output is correct
17 Correct 137 ms 3924 KB Output is correct
18 Correct 37 ms 3928 KB Output is correct
19 Correct 42 ms 4692 KB Output is correct
20 Correct 78 ms 4436 KB Output is correct
21 Execution timed out 4014 ms 3156 KB Time limit exceeded
22 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 43 ms 1128 KB Output is correct
3 Correct 69 ms 1112 KB Output is correct
4 Correct 117 ms 3920 KB Output is correct
5 Correct 40 ms 3920 KB Output is correct
6 Correct 96 ms 3924 KB Output is correct
7 Correct 145 ms 3920 KB Output is correct
8 Correct 137 ms 3920 KB Output is correct
9 Correct 45 ms 3984 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 38 ms 4052 KB Output is correct
12 Correct 70 ms 4012 KB Output is correct
13 Correct 98 ms 3924 KB Output is correct
14 Correct 38 ms 3920 KB Output is correct
15 Correct 112 ms 3960 KB Output is correct
16 Correct 147 ms 4064 KB Output is correct
17 Correct 138 ms 3924 KB Output is correct
18 Correct 37 ms 3916 KB Output is correct
19 Execution timed out 4082 ms 468 KB Time limit exceeded
20 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 43 ms 1128 KB Output is correct
3 Correct 69 ms 1112 KB Output is correct
4 Correct 117 ms 3920 KB Output is correct
5 Correct 40 ms 3920 KB Output is correct
6 Correct 96 ms 3924 KB Output is correct
7 Correct 145 ms 3920 KB Output is correct
8 Correct 137 ms 3920 KB Output is correct
9 Correct 45 ms 3984 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 38 ms 3920 KB Output is correct
12 Correct 66 ms 4060 KB Output is correct
13 Correct 88 ms 4124 KB Output is correct
14 Correct 39 ms 3896 KB Output is correct
15 Correct 92 ms 3920 KB Output is correct
16 Correct 141 ms 3880 KB Output is correct
17 Correct 137 ms 3924 KB Output is correct
18 Correct 37 ms 3928 KB Output is correct
19 Correct 42 ms 4692 KB Output is correct
20 Correct 78 ms 4436 KB Output is correct
21 Execution timed out 4014 ms 3156 KB Time limit exceeded
22 Halted 0 ms 0 KB -