Submission #698826

#	Time	Username	Problem	Language	Result	Execution time	Memory
698826		sharaelong	Koala Game (APIO17_koala)	C++17	100 / 100	59 ms	440 KiB

koala

#include "koala.h"
#include <algorithm>
#include <bits/stdc++.h>
#include <ostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 100;

int B[MAX_N], R[MAX_N];

int minValue(int N, int W) {
    // TODO: Implement Subtask 1 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    memset(B, 0, sizeof B);
    B[0] = 1;
    playRound(B, R);
    int zero_pos = find(R, R+N, 0) - R;
    return zero_pos;
}

int maxValue(int N, int W) {
    // TODO: Implement Subtask 2 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.

    for (int i=0; i<N; ++i) B[i] = 1;
    playRound(B, R);
    vector<int> half_large;
    for (int i=0; i<N; ++i) {
        if (R[i] == 2) half_large.push_back(i);
    }
    assert(half_large.size() == 50);

    memset(B, 0, sizeof B);
    for (int i: half_large) B[i] = 2;
    playRound(B, R);
    vector<int> quarter_large;
    for (int i=0; i<N; ++i) {
        if (R[i] == 3) quarter_large.push_back(i);
    }

    memset(B, 0, sizeof B);
    for (int i: quarter_large) B[i] = 4;
    playRound(B, R);
    vector<int> ninetyone_large;
    for (int i=0; i<N; ++i) {
        if (R[i] > 1) ninetyone_large.push_back(i);
    }

    memset(B, 0, sizeof B);
    for (int i: ninetyone_large) B[i] = 11;
    playRound(B, R);
    return find(R, R+N, 12) - R;
}

void sub3_helper(int x) {
    memset(B, 0, sizeof B);
    B[0] = B[1] = x;
    playRound(B, R);
}

int greaterValue(int N, int W) {
    // TODO: Implement Subtask 3 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.

    sub3_helper(4);
    if (R[0] == R[1]) {
        if (R[0] == 0) {
            sub3_helper(2);
            if (R[0] != R[1]) {
                // cout << "2 ";
                return R[0] < R[1];
            }
            sub3_helper(1);
            // cout << "1 ";
            return R[0] < R[1];
        } else {
            sub3_helper(8);
            // cout << "8 ";
            return R[0] < R[1];
        }
    } else {
        // cout << "4 ";
        return R[0] < R[1];
    }
}

void sub4_helper(int i, int j) {
    B[i] = B[j] = 100;
    playRound(B, R);
    B[i] = B[j] = 0;
}

void sub5_helper(int N, vector<int>& arr, int thres) {
    // cout << thres << ' ';
    // for (int x: arr) cout << x << ' ';
    // cout << endl;
    if (arr.size() == 1) return;
    if (arr.size() == 0) assert(false);
    
    memset(B, 0, sizeof B);
    for (int x: arr) B[x] = thres;
    playRound(B, R);

    vector<int> big, small;
    for (int i=0; i<N; ++i) {
        if (R[i] >= thres+1) big.push_back(i);
    }
    for (int x: arr) {
        if (find(big.begin(), big.end(), x) == big.end()) small.push_back(x);
    }

    if (small.size() == 0) {
        sub5_helper(N, big, thres+1);
    } else {
        sub5_helper(N, small, thres);
        sub5_helper(N, big, thres);
    }
    arr.clear();
    for (int x: small) arr.push_back(x);
    for (int x: big) arr.push_back(x);
}

void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        // TODO: Implement Subtask 4 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
        vector<int> ord = { 0 };
        for (int i=1; i<N; ++i) {
            int l = 0, r = i; // bar model
            while (l < r) {
                int mid = (l+r) / 2;
                sub4_helper(ord[mid], i);
                if (R[ord[mid]] < R[i]) {
                    l = mid+1;
                } else {
                    r = mid;
                }
            }
            vector<int> tmp;
            for (int i=0; i<l; ++i) tmp.push_back(ord[i]);
            tmp.push_back(i);
            for (int i=l; i<ord.size(); ++i) tmp.push_back(ord[i]);
            ord = tmp;
        }
        for (int i=0; i<N; ++i) P[ord[i]] = i+1;
    } else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.

        int min_pos = minValue(N, W);
        
        vector<vector<int>> q(8);

        // [1, 100] -> [1], [2, 50], [51, 100]
        fill(B, B+N, 1);
        playRound(B, R);
        for (int i=0; i<N; ++i) {
            if (R[i] >= 2) q[4].push_back(i);
            else q[0].push_back(i);
        }
        q[0].erase(find(q[0].begin(), q[0].end(), min_pos));

        // [1, 50] -> [1, 25], [26, 50]
        memset(B, 0, sizeof B);
        for (int x: q[0]) B[x] = 1;
        playRound(B, R);
        for (int i=0; i<N; ++i) {
            if (R[i] >= 2) {
                q[2].push_back(i);
                auto it = find(q[0].begin(), q[0].end(), i);
                q[0].erase(it);
            }
        }

        // [2, 25] -> [2, 13], [14, 25]
        memset(B, 0, sizeof B);
        for (int x: q[0]) B[x] = 1;
        playRound(B, R);
        for (int i=0; i<N; ++i) {
            if (R[i] >= 2) {
                q[1].push_back(i);
                auto it = find(q[0].begin(), q[0].end(), i);
                q[0].erase(it);
            }
        }

        // [2, 13] -> [2, 7], [8, 13]
        vector<int> lq0, rq0;
        memset(B, 0, sizeof B);
        for (int x: q[0]) B[x] = 1;
        playRound(B, R);
        for (int i=0; i<N; ++i) {
            if (R[i] >= 2) rq0.push_back(i);
        }
        for (int x: q[0]) {
            if (find(rq0.begin(), rq0.end(), x) == rq0.end()) lq0.push_back(x);
        }

        // [26, 50] -> [26, 38], [39, 50]
        memset(B, 0, sizeof B);
        for (int x: q[1]) B[x] = 2;
        for (int x: q[2]) B[x] = 3;
        playRound(B, R);
        for (int i=0; i<N; ++i) {
            if (R[i] >= 4) {
                q[3].push_back(i);
                auto it = find(q[2].begin(), q[2].end(), i);
                q[2].erase(it);
            }
        }

        // [51, 100] -> [51, 75], [76, 100]
        memset(B, 0, sizeof B);
        for (int x: q[4]) B[x] = 2;
        playRound(B, R);
        for (int i=0; i<N; ++i) {
            if (R[i] >= 3) {
                q[6].push_back(i);
                auto it = find(q[4].begin(), q[4].end(), i);
                q[4].erase(it);
            }
        }

        // [51, 75] -> [51, 63], [64, 75]
        memset(B, 0, sizeof B);
        for (int x: q[0]) B[x] = 1;
        for (int x: q[1]) B[x] = 1;
        for (int x: q[4]) B[x] = 3;
        playRound(B, R);
        for (int i=0; i<N; ++i) {
            if (R[i] >= 4) {
                q[5].push_back(i);
                auto it = find(q[4].begin(), q[4].end(), i);
                q[4].erase(it);
            }
        }

        // [76, 100] -> [76, 88], [89, 100]
        memset(B, 0, sizeof B);
        for (int x: q[6]) B[x] = 3;
        playRound(B, R);
        for (int i=0; i<N; ++i) {
            if (R[i] >= 4) {
                q[7].push_back(i);
                auto it = find(q[6].begin(), q[6].end(), i);
                q[6].erase(it);
            }
        }

        sub5_helper(N, lq0, 2);
        sub5_helper(N, rq0, 3);
        sub5_helper(N, q[1], 4);
        for (int i=2; i<7; ++i) sub5_helper(N, q[i], 7);
        sub5_helper(N, q[7], 8);
        // for (int i=6; i<8; ++i) sub5_helper(N, q[i], 8);

        P[min_pos] = 1;
        for (int i=2; i<=7; ++i) P[lq0[i-2]] = i;
        for (int i=8; i<=13; ++i) P[rq0[i-8]] = i;
        for (int i=14; i<=25; ++i) P[q[1][i-14]] = i;
        for (int i=26; i<=38; ++i) P[q[2][i-26]] = i;
        for (int i=39; i<=50; ++i) P[q[3][i-39]] = i;
        for (int i=51; i<=63; ++i) P[q[4][i-51]] = i;
        for (int i=64; i<=75; ++i) P[q[5][i-64]] = i;
        for (int i=76; i<=88; ++i) P[q[6][i-76]] = i;
        for (int i=89; i<=100; ++i) P[q[7][i-89]] = i;
        
        
        // memset(B, 0, sizeof B);
        // for (int i=13; i<25; ++i) B[i] = 2;
        // for (int i=25; i<50; ++i) B[i] = 3;
        // playRound(B, R);
        // for (int i=0; i<N; ++i) cout << R[i] << ' ';
        // cout << endl;
        // cout << find(R, R+N, 4) - R << endl;
    }
}

Compilation message (stderr)

koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:149:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |             for (int i=l; i<ord.size(); ++i) tmp.push_back(ord[i]);
      |                           ~^~~~~~~~~~~

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