Submission #969959

#	Time	Username	Problem	Language	Result	Execution time	Memory
969959		socpite	Koala Game (APIO17_koala)	C++14	100 / 100	63 ms	596 KiB

koala

#include "koala.h"
#include<bits/stdc++.h>
using namespace std;

#define isz(x) (int)x.size()

int B[105], R[105];

int minValue(int N, int W) {
    B[0] = 1;
    playRound(B, R);
    if(R[0] == 2)for(int i = 0; i < N; i++)if(R[i] == 0)return i;
    return 0;
}
vector<int> search_set = {1, 2, 3, 5, 8};

int maxValue(int N, int W) {
    vector<int> vec = {1, 2, 4, 11};
    vector<int> good(N);
    iota(good.begin(), good.end(), 0);
    for(auto v: vec){
        fill(B, B + N, 0);
        for(auto id: good)B[id] = v;
        playRound(B, R);
        good.clear();
        for(int i = 0; i < N; i++)if(R[i] > v)good.push_back(i);
    }
    return good.back();
}

int greaterValue(int N, int W) {
    int l = 0, r = search_set.size()-1;
    while(l <= r){
        int md = (l+r)>>1;
        int mid = search_set[md];
        B[0] = B[1] = mid;
        playRound(B, R);
        if (R[0] > mid and R[1] <= mid) return 0;
        if (R[1] > mid and R[0] <= mid) return 1;
        if(R[0] > mid && R[1] > mid)l = md + 1;
        else r = md - 1;
    }
    return 0;

    // k p0 <= sum (k+1)so dau tien < p1
}

int n;

// 1-3, 3-9, 6-18, 15-45, 36-100
int bound[9][2] = {
    {0, 0},
    {0, 4},
    {2, 10},
    {5, 19},
    {9, 31},
    {14, 46},
    {20, 64},
    {27, 85},
    {35, 101}
};

int cbound[105][2];

int cnt[105][2];
bool recmp[105][105];

bool cmp(int a, int b){
    // assert(a != b);
    if(recmp[a][b])return 1;
    if(recmp[b][a])return 0;
    int la = max(cnt[a][0] - 1, cbound[a][0]), ra = min(100 - cnt[a][1], cbound[a][1]);
    int lb = max(cnt[b][0] - 1, cbound[b][0]), rb = min(100 - cnt[b][1], cbound[b][1]);
    if(la >= rb){
        cnt[a][0]++;
        cnt[b][1]++;
        recmp[b][a] = 1;
        cbound[a][0] = max(cbound[a][0], cbound[b][0]);
        cbound[b][1] = min(cbound[b][1], cbound[a][1]);
        return 0;
    }
    if(lb >= ra){
        recmp[a][b] = 1;
        cnt[b][0]++;
        cnt[a][1]++;
        cbound[b][0] = max(cbound[b][0], cbound[a][0]);
        cbound[a][1] = min(cbound[a][1], cbound[b][1]);
        return 1;
    }
    int l = -1, r = -1;
    for(int i = 0; i < search_set.size(); i++){
        if(bound[search_set[i]][0] >= min(ra, rb) || bound[search_set[i]][1] <= max(la, lb))continue;
        if(l == -1)l = i;
        r = i;
    }
    while(l <= r){
        int md = (l+r)>>1;
        int mid = search_set[md];
        fill(B, B+n, 0);
        B[a] = B[b] = mid;
        playRound(B, R);
        // cout << mid << " " << R[a] << " " << R[b] << endl;
        if (R[a] > mid and R[b] <= mid) {
            cnt[a][0]++;
            cnt[b][1]++;
            recmp[b][a] = 1;
            cbound[a][0] = max(cbound[a][0], cbound[b][0]);
            cbound[b][1] = min(cbound[b][1], cbound[a][1]);
            return 0;
        }
        if (R[b] > mid and R[a] <= mid) {
            cnt[b][0]++;
            cnt[a][1]++;
            recmp[a][b] = 1; 
            cbound[b][0] = max(cbound[b][0], cbound[a][0]);
            cbound[a][1] = min(cbound[a][1], cbound[b][1]);
            return 1;
        }
        if(R[a] > mid && R[b] > mid){
            l = md + 1;
            cbound[a][0] = max(cbound[a][0], bound[mid][1]);
            cbound[b][0] = max(cbound[b][0], bound[mid][1]);
        }
        else {
            r = md - 1;
            cbound[a][1] = min(cbound[a][1], bound[mid][0]);
            cbound[b][1] = min(cbound[b][1], bound[mid][0]);
        }
    }
    // assert(false);
    return 0;
}

bool cmp_subtask_4(int a, int b){
    fill(B, B+n, 0);
    B[a] = B[b] = n;
    playRound(B, R);
    return R[a] < R[b];
}

mt19937 rng_lmao(69420);

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

void allValues(int N, int W, int *P) {
    n = N;
    if (W == 2*N) {
        vector<int> vec(N);
        iota(vec.begin(), vec.end(), 0);
        stable_sort(vec.begin(), vec.end(), cmp_subtask_4);
        for(int i = 0; i < N; i++)P[vec[i]] = i+1;
    } else {
        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) {
            P[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);
        
    }
}

Compilation message (stderr)

koala.cpp: In function 'bool cmp(int, int)':
koala.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i = 0; i < search_set.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 53 / 53