oj.uz

Submission #385192

# Submission time Handle Problem Language Result Execution time Memory
385192 2021-04-03T13:43:45 Z phathnv Koala Game (APIO17_koala) C++11
100 / 100
 91 ms 492 KB 
#include <bits/stdc++.h>
#include "koala.h"

using namespace std;

int minValue(int N, int W) {
    int b[N], r[N];
    memset(b, 0, sizeof(b));
    b[0] = 1;
    playRound(b, r);
    for(int i = 0; i < N; i++)
        if (r[i] == 0)
            return i;
    return 0;
}

int maxValue(int N, int W) {
    vector<int> candidates;
    for(int i = 0; i < N; i++)
        candidates.push_back(i);
    while (candidates.size() > 1){
        int b[N], r[N];
        memset(b, 0, sizeof(b));
        int c = min(12, W / (int) candidates.size());
        for(int ind : candidates)
            b[ind] = c;
        playRound(b, r);
        vector<int> nxt;
        for(int i = 0; i < N; i++)
            if (b[i] == c && r[i] > c)
                nxt.push_back(i);
        candidates = nxt;
    }
    return candidates.front();
}

int greaterValue(int N, int W) {
    int val[6] = {1, 2, 4, 6, 7, 8};
    int lo = 0, hi = 5;
    while (lo <= hi){
        int mid = (lo + hi) >> 1;
        int b[N], r[N];
        memset(b, 0, sizeof(b));
        b[0] = b[1] = val[mid];
        playRound(b, r);
        if (r[0] > b[0] && r[1] <= b[1])
            return 0;
        else if (r[0] <= b[0] && r[1] > b[1])
            return 1;
        else if (r[0] <= b[0] && r[1] <= b[1])
            hi = mid - 1;
        else
            lo = mid + 1;
    }

    return 0;
}

int ptr;
int key[2][99] = {
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 3, 1, 3, 1, 1, 2, 3, 4, 2, 3, 4, 4, 1, 2, 3, 3, 4, 1, 5, 1, 2, 2, 3, 5, 3, 4, 5, 2, 5, 2, 3, 4, 5, 4, 4, 6, 1, 2, 3, 5, 6, 3, 4, 6, 5, 6, 1, 4, 5, 6, 1, 7, 1, 2, 2, 2, 3, 4, 5, 7, 3, 4, 7, 5, 6, 7, 2, 5, 6, 7, 2, 2, 3, 4, 5, 6, 8, 3, 4, 6, 8, 5, 8, 6, 8},
    {2, 3, 4, 15, 17, 21, 26, 35, 52, 4, 5, 26, 35, 53, 5, 6, 35, 53, 7, 53, 8, 53, 9, 54, 10, 11, 12, 14, 16, 18, 22, 27, 36, 54, 2, 18, 22, 28, 37, 55, 2, 55, 2, 3, 8, 9, 10, 10, 11, 13, 14, 16, 19, 22, 28, 37, 56, 3, 28, 37, 56, 3, 4, 14, 16, 19, 23, 28, 38, 56, 4, 5, 23, 28, 38, 56, 5, 6, 28, 38, 57, 7, 38, 57, 8, 57, 9, 57, 10, 11, 12, 13, 15, 17, 19, 23, 29, 38, 57}
};
void solve(int N, int W, int l, int r, vector<int> candidates, int *P){
    assert((int) candidates.size() == r - l + 1);
    if (candidates.size() == 1){
        P[candidates.front()] = l;
        return;
    }

    vector<int> toLeft, toRight;
    int k = key[W / N - 1][ptr++];
    while (toLeft.empty() || toRight.empty()){
        int b[N], r[N];
        memset(b, 0, sizeof(b));
        for(int x : candidates)
            b[x] = k;
        playRound(b, r);
        toLeft.clear();
        toRight.clear();
        for(int x : candidates)
            if (r[x] <= b[x])
                toLeft.push_back(x);
            else
                toRight.push_back(x);
    }
    solve(N, W, l, l + toLeft.size() - 1, toLeft, P);
    solve(N, W, l + toLeft.size(), r, toRight, P);
}

void allValues(int N, int W, int *P) {
    ptr = 0;
    vector<int> a;
    for(int i = 0; i < N; i++)
        a.push_back(i);
    solve(N, W, 1, N, a, P);
}

Subtask #1
4.0 / 4.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 364 KB Output is correct
2 Correct 19 ms 364 KB Output is correct
3 Correct 22 ms 364 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 83 ms 376 KB Output is correct
2 Correct 91 ms 492 KB Output is correct
3 Correct 82 ms 364 KB Output is correct
4 Correct 79 ms 364 KB Output is correct
5 Correct 80 ms 364 KB Output is correct
6 Correct 83 ms 492 KB Output is correct
7 Correct 80 ms 364 KB Output is correct
8 Correct 80 ms 424 KB Output is correct
9 Correct 79 ms 364 KB Output is correct
10 Correct 79 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 364 KB Output is correct
2 Correct 9 ms 364 KB Output is correct
3 Correct 9 ms 364 KB Output is correct
4 Correct 9 ms 492 KB Output is correct
5 Correct 9 ms 364 KB Output is correct
6 Correct 9 ms 364 KB Output is correct
7 Correct 9 ms 364 KB Output is correct
8 Correct 9 ms 364 KB Output is correct
9 Correct 9 ms 364 KB Output is correct
10 Correct 9 ms 364 KB Output is correct
11 Correct 9 ms 364 KB Output is correct
12 Correct 9 ms 364 KB Output is correct
13 Correct 9 ms 364 KB Output is correct
14 Correct 9 ms 364 KB Output is correct
15 Correct 9 ms 364 KB Output is correct
16 Correct 9 ms 364 KB Output is correct
17 Correct 9 ms 364 KB Output is correct
18 Correct 9 ms 364 KB Output is correct
19 Correct 9 ms 364 KB Output is correct
20 Correct 9 ms 364 KB Output is correct

Subtask #5
53.0 / 53.0

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