oj.uz

Submission #969955

# Submission time Handle Problem Language Result Execution time Memory
969955 2024-04-26T01:59:00 Z CDuong Koala Game (APIO17_koala) C++17
53 / 100
 4 ms 600 KB 
#include "koala.h"
#include <bits/stdc++.h>
#define isz(x) (int)x.size()
using namespace std;
 
int B[105], R[105];
 
int minValue(int N, int W) {
    return 0;
}
 
 
int maxValue(int N, int W) {
    return 0;
}
 
int greaterValue(int N, int W) {
    return 0;
}

int calc(int start, int len) {
    len = min(len, start);
    return start * len - len * (len - 1) / 2;
}

int transform(int x, int n, int val) {
    int nx = max(x, n - n / (val + 1) + 1);
    int start = x - 1 - (n - (n - nx + 1) * (val + 1));
    while (nx <= n and nx <= calc(start, val + 1)) {
        ++nx, start -= val + 1;
    }
    return nx;
}

pair<int, int> vis[105][105];

void allValues(int n, int w, int *ans) {
    if (w == 2 * n) {
        return;
    }
    // auto check = [&](int l, int r) -> bool {
    //     if (l + 1 == r) {
    //         vis[l][r] = {1, 1};
    //         return true;
    //     }
    //     for (int i = r / (r - l); i >= 1; --i) {
    //         // int nl = transform(l, r - 1, i);
    //         // if (l < nl and nl < r) {
    //             fill(B, B + n, 0);
    //             for (int idx_ = l - 1; idx_ < r - 1; ++idx_) B[idx_] = i;
    //             playRound(B, R);
    //             vector<int> left, right;
    //             for (int idx_ = l - 1; idx_ < r - 1; ++idx_) {
    //                 if (R[idx_] > i) right.emplace_back(idx_);
    //                 else left.emplace_back(idx_);
    //             }
    //             // self(self, left, l, l + isz(left));
    //             // self(self, right, r - isz(right), r);
    //             assert(l + isz(left) == r - isz(right));
    //             // assert(l + isz(left) == nl);
    //             if (vis[l][l + isz(left)].first and vis[r - isz(right)][r].first) {
    //                 vis[l][r] = {i, l + isz(left)};
    //                 return true;
    //             }
    //         // }
    //     }
    //     return false;
    // };

    // for (int len = 1; len <= n; ++len) {
    //     for (int i = 1; i <= n - len + 1; ++i) if (check(i, i + len)) {
    //         // cout << "vis[" << i << "][" << i + len << "] = {" << vis[i][i + len].first << ", " << vis[i][i + len].second << "};\n";
    //     }
    // }

    // auto dfs = [&](auto self, int l, int r) -> void {
    //     if (l + 1 == r) return;
    //     cout << "vis[" << l << "][" << r << "] = {" << vis[l][r].first << ", " << vis[l][r].second << "};\n";
    //     self(self, l, vis[l][r].second);
    //     self(self, vis[l][r].second, r);
    // };
    // dfs(dfs, 1, 101);
    
vis[1][101] = {1, 51};
vis[1][51] = {1, 26};
vis[1][26] = {1, 14};
vis[1][14] = {1, 8};
vis[1][8] = {1, 5};
vis[1][5] = {1, 3};
vis[1][3] = {1, 2};
vis[3][5] = {2, 4};
vis[5][8] = {2, 7};
vis[5][7] = {3, 6};
vis[8][14] = {2, 11};
vis[8][11] = {3, 10};
vis[8][10] = {4, 9};
vis[11][14] = {4, 13};
vis[11][13] = {5, 12};
vis[14][26] = {2, 20};
vis[14][20] = {3, 18};
vis[14][18] = {4, 17};
vis[14][17] = {5, 16};
vis[14][16] = {5, 15};
vis[18][20] = {6, 19};
vis[20][26] = {4, 24};
vis[20][24] = {6, 23};
vis[20][23] = {7, 22};
vis[20][22] = {6, 21};
vis[24][26] = {7, 25};
vis[26][51] = {2, 39};
vis[26][39] = {3, 34};
vis[26][34] = {4, 31};
vis[26][31] = {6, 30};
vis[26][30] = {7, 29};
vis[26][29] = {8, 28};
vis[26][28] = {7, 27};
vis[31][34] = {9, 33};
vis[31][33] = {8, 32};
vis[34][39] = {7, 38};
vis[34][38] = {9, 37};
vis[34][37] = {9, 36};
vis[34][36] = {8, 35};
vis[39][51] = {4, 47};
vis[39][47] = {5, 45};
vis[39][45] = {7, 44};
vis[39][44] = {8, 43};
vis[39][43] = {10, 42};
vis[39][42] = {10, 41};
vis[39][41] = {9, 40};
vis[45][47] = {10, 46};
vis[47][51] = {12, 50};
vis[47][50] = {11, 49};
vis[47][49] = {10, 48};
vis[51][101] = {2, 76};
vis[51][76] = {3, 66};
vis[51][66] = {4, 61};
vis[51][61] = {6, 58};
vis[51][58] = {8, 57};
vis[51][57] = {9, 56};
vis[51][56] = {11, 55};
vis[51][55] = {12, 54};
vis[51][54] = {11, 53};
vis[51][53] = {10, 52};
vis[58][61] = {12, 60};
vis[58][60] = {11, 59};
vis[61][66] = {13, 65};
vis[61][65] = {13, 64};
vis[61][64] = {12, 63};
vis[61][63] = {11, 62};
vis[66][76] = {7, 74};
vis[66][74] = {9, 73};
vis[66][73] = {10, 72};
vis[66][72] = {12, 71};
vis[66][71] = {14, 70};
vis[66][70] = {14, 69};
vis[66][69] = {13, 68};
vis[66][68] = {12, 67};
vis[74][76] = {12, 75};
vis[76][101] = {4, 92};
vis[76][92] = {5, 87};
vis[76][87] = {7, 84};
vis[76][84] = {10, 83};
vis[76][83] = {11, 82};
vis[76][82] = {13, 81};
vis[76][81] = {16, 80};
vis[76][80] = {15, 79};
vis[76][79] = {13, 78};
vis[76][78] = {12, 77};
vis[84][87] = {14, 86};
vis[84][86] = {13, 85};
vis[87][92] = {16, 91};
vis[87][91] = {15, 90};
vis[87][90] = {14, 89};
vis[87][89] = {13, 88};
vis[92][101] = {11, 100};
vis[92][100] = {12, 99};
vis[92][99] = {14, 98};
vis[92][98] = {16, 97};
vis[92][97] = {17, 96};
vis[92][96] = {16, 95};
vis[92][95] = {15, 94};
vis[92][94] = {14, 93};

    auto dfs = [&](auto self, vector<int> idx, int l, int r) -> void {
        if (l + 1 == r) {
            ans[idx.front()] = l;
            return;
        }
        fill(B, B + n, 0);
        int val = vis[l][r].first;
        // cout << l << " " << r << " " << val << endl;
        for (int idx_ : idx) B[idx_] = val;
        playRound(B, R);
        vector<int> left, right;
        for (int idx_ : idx) {
            if (R[idx_] > val) right.emplace_back(idx_);
            else left.emplace_back(idx_);
        }
        // cout << l << " " << r << " " << l + isz(left) << " " << r - isz(right) << " " << vis[l][r].second << endl;
        assert(l + isz(left) == vis[l][r].second);
        assert(r - isz(right) == vis[l][r].second);
        self(self, left, l, l + isz(left));
        self(self, right, r - isz(right), r);
    };
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    dfs(dfs, idx, 1, n + 1);

    // auto cook = [&](auto self, vector<int> idx, int l, int r) -> void {
    //     if (l == r) ans[idx.front()] = 0;
    //     for (int i = r / (r - l); i >= 1; --i) {
    //         int nl = transform(l, r, i);
    //         if (l < nl and nl < r) {
    //             fill(B, B + n, 0);
    //             for (auto idx_ : idx) B[idx_] = i;
    //             playRound(B, R);
    //             vector<int> left, right;
    //             for (auto idx_ : idx) {
    //                 if (R[idx_] > i) right.emplace_back(idx_);
    //                 else left.emplace_back(idx_);
    //             }
    //             self(self, left, l, l + isz(left));
    //             self(self, right, r - isz(right), r);
    //             assert(l + isz(left) == r - isz(right));
    //             return;
    //         }
    //         assert(0);
    //     }
    // };
    // cook(cook, idx, 1, n + 1);
}

// int main() {
//     cout << transform(92, 100, 11) << endl;
// }

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
53.0 / 53.0

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