oj.uz

Submission #255354

# Submission time Handle Problem Language Result Execution time Memory
255354 2020-07-31T18:55:40 Z Osama_Alkhodairy Koala Game (APIO17_koala) C++17
100 / 100
 89 ms 512 KB 
#include <bits/stdc++.h>
#include "koala.h"
//~ #include "grader.cpp"
using namespace std;

int n;
vector <int> ans;

bool cmp(int i, int j){
    int B[n], R[n];
    for(int i = 0 ; i < n ; i++){
        B[i] = R[i] = 0;
    }
    int l = 1, r = 9;
    while(l <= r){
        int mid = (l + r) / 2;
        B[i] = B[j] = mid;
        playRound(B, R);
        if((R[i] > B[i]) == (R[j] > B[j])){
            if(R[i] > B[j]) l = mid + 1;
            else r = mid - 1;
        }
        else return R[j] > B[j];
    }
    assert(false);
}
bool cmp2(int i, int j){
    int B[n], R[n];
    for(int i = 0 ; i < n ; i++){
        B[i] = R[i] = 0;
    }
    B[i] = B[j] = 100;
    playRound(B, R);
    return R[j] > B[j];
}
int calc(int l, int r, int g){
    int mx = 0, mx_ret = 0;
    for(int i = 0 ; i <= n - (r - l + 1) ; i++){
        int cur_ops = n;
        int cur_sum = 0;
        int f = i;
        int cur_pos = n;
        while(f > 0){
            if(l <= cur_pos && cur_pos <= r){
                cur_pos--;
                continue;
            }
            if(cur_pos <= 0) break;
            f--;
            cur_sum += cur_pos;
            cur_pos--;
            cur_ops--;
        }
        cur_pos = r;
        int cur_ret = 0;
        while(l <= cur_pos){
            if(g + 1 > cur_ops) break;
            cur_sum += cur_pos;
            cur_pos--;
            cur_ops -= g + 1;
            cur_ret++;
        }
        if(cur_sum >= mx){
            mx = cur_sum;
            mx_ret = cur_ret;
        }
    }
    return mx_ret;
}
void solve(int l, int r, vector <int> cur){
    if(r < l) return;
    if(l == r){
        ans[cur[0]] = l;
        return;
    }
    int opt = (r - l + 1) / 2;
    int best_i = 0, best = calc(l, r, 0);
    for(int i = 0 ; i <= 100 ; i++){
        int cur = calc(l, r, i);
        if(abs(opt - cur) < abs(opt - best)){
            best = cur;
            best_i = i;
        }
    }
    int B[n], R[n];
    for(int i = 0 ; i < n ; i++){
        B[i] = R[i] = 0;
    }
    for(auto &i : cur){
        B[i] = best_i;
    }
    playRound(B, R);
    vector <int> s, e;
    for(auto &i : cur){
        if(R[i] > B[i]) e.push_back(i);
        else s.push_back(i);
    }
    solve(l, l + (int)s.size() - 1, s);
    solve(r - (int)e.size() + 1, r, e);
}
int minValue(int N, int W) {
    n = N;
    int B[n], R[n];
    for(int i = 0 ; i < n ; i++){
        B[i] = R[i] = 0;
    }
    B[0]++;
    playRound(B, R);
    for(int i = 0 ; i < n ; i++){
        if(B[i] >= R[i]) return i;
    }
    return 0;
}
int maxValue(int N, int W) {
    n = N;
    int B[n], R[n];
    vector <int> cands;
    for(int i = 0 ; i < n ; i++){
        cands.push_back(i);
    }
    while(cands.size() > 1){
        for(int i = 0 ; i < n ; i++){
            B[i] = R[i] = 0;
        }
        int cur = W / cands.size();
        for(auto &i : cands) B[i] = cur;
        playRound(B, R);
        cands.clear();
        for(int i = 0 ; i < n ; i++){
            if(B[i] == cur && R[i] > B[i]){
                cands.push_back(i);
            }
        }
    }
    return cands[0];
}
int greaterValue(int N, int W) {
    n = N;
    if(cmp(0, 1)) return 1;
    return 0;
}
void allValues(int N, int W, int *P) {
    n = N;
    if (W == 2*N) {
        vector <int> all;
        for(int i = 0 ; i < n ; i++){
            all.push_back(i);
        }
        stable_sort(all.begin(), all.end(), cmp2);
        for(int i = 0 ; i < n ; i++){
            P[all[i]] = i + 1;
        }
    } else {
        ans.resize(n);
        vector <int> all;
        for(int i = 0 ; i < n ; i++){
            all.push_back(i);
        }
        solve(1, n, all);
        for(int i = 0 ; i < n ; i++){
            P[i] = ans[i];
        }
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 384 KB Output is correct
2 Correct 17 ms 384 KB Output is correct
3 Correct 19 ms 504 KB Output is correct
4 Correct 18 ms 384 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 384 KB Output is correct
2 Correct 88 ms 384 KB Output is correct
3 Correct 73 ms 512 KB Output is correct
4 Correct 74 ms 384 KB Output is correct
5 Correct 76 ms 384 KB Output is correct
6 Correct 75 ms 384 KB Output is correct
7 Correct 82 ms 384 KB Output is correct
8 Correct 76 ms 384 KB Output is correct
9 Correct 89 ms 384 KB Output is correct
10 Correct 76 ms 504 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 384 KB Output is correct
2 Correct 55 ms 384 KB Output is correct
3 Correct 50 ms 384 KB Output is correct
4 Correct 47 ms 376 KB Output is correct
5 Correct 48 ms 504 KB Output is correct
6 Correct 48 ms 384 KB Output is correct
7 Correct 48 ms 384 KB Output is correct
8 Correct 48 ms 384 KB Output is correct
9 Correct 49 ms 384 KB Output is correct
10 Correct 50 ms 384 KB Output is correct
11 Correct 49 ms 504 KB Output is correct
12 Correct 21 ms 384 KB Output is correct
13 Correct 53 ms 504 KB Output is correct
14 Correct 43 ms 384 KB Output is correct
15 Correct 42 ms 376 KB Output is correct
16 Correct 45 ms 384 KB Output is correct
17 Correct 44 ms 376 KB Output is correct
18 Correct 43 ms 384 KB Output is correct
19 Correct 45 ms 504 KB Output is correct
20 Correct 44 ms 504 KB Output is correct

Subtask #5
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 384 KB Output is correct
2 Correct 64 ms 384 KB Output is correct
3 Correct 66 ms 384 KB Output is correct
4 Correct 64 ms 388 KB Output is correct
5 Correct 66 ms 384 KB Output is correct
6 Correct 66 ms 504 KB Output is correct
7 Correct 65 ms 384 KB Output is correct
8 Correct 69 ms 392 KB Output is correct
9 Correct 66 ms 384 KB Output is correct
10 Correct 67 ms 384 KB Output is correct
11 Correct 65 ms 384 KB Output is correct
12 Correct 66 ms 384 KB Output is correct
13 Correct 64 ms 384 KB Output is correct
14 Correct 64 ms 384 KB Output is correct
15 Correct 74 ms 508 KB Output is correct
16 Correct 64 ms 384 KB Output is correct
17 Correct 67 ms 384 KB Output is correct
18 Correct 64 ms 384 KB Output is correct
19 Correct 66 ms 384 KB Output is correct
20 Correct 65 ms 384 KB Output is correct
21 Correct 76 ms 504 KB Output is correct
22 Correct 65 ms 384 KB Output is correct
23 Correct 67 ms 384 KB Output is correct
24 Correct 67 ms 384 KB Output is correct
25 Correct 77 ms 384 KB Output is correct
26 Correct 67 ms 504 KB Output is correct
27 Correct 65 ms 384 KB Output is correct
28 Correct 65 ms 384 KB Output is correct
29 Correct 65 ms 384 KB Output is correct
30 Correct 64 ms 504 KB Output is correct
31 Correct 66 ms 384 KB Output is correct
32 Correct 64 ms 384 KB Output is correct
33 Correct 65 ms 384 KB Output is correct
34 Correct 64 ms 384 KB Output is correct
35 Correct 65 ms 388 KB Output is correct
36 Correct 64 ms 384 KB Output is correct
37 Correct 64 ms 384 KB Output is correct
38 Correct 65 ms 384 KB Output is correct
39 Correct 65 ms 384 KB Output is correct
40 Correct 65 ms 388 KB Output is correct