Submission #1104107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104107		makrav	Koala Game (APIO17_koala)	C++14	100 / 100	46 ms	644 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define sz(x) (int) (x).size()

int minValue(int N, int W) {
    int R[100], B[100];
    for (int i = 0; i < 100; i++) B[i] = 0;
    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) {
    int B[100], R[100];
    for (int i = 0; i < N; i++) {
        B[i] = 1;
    }
    playRound(B, R);
    vector<int> ps;
    for (int i = 0; i < N; i++) {
        if (R[i] == 2) ps.push_back(i);
    }
    for (int i = 0; i < N; i++) B[i] = 0;
    for (int i = 0; i < 50; i++) B[ps[i]] = 2;
    playRound(B, R);
    ps.clear();
    for (int i = 0; i < N; i++) {
        if (R[i] == 3) ps.push_back(i);
    }
    for (int i = 0; i < N; i++) B[i] = 0;
    for (int i = 0; i < 25; i++) B[ps[i]] = 4;
    playRound(B, R);
    ps.clear();
    for (int i = 0; i < N; i++) {
        if (R[i] == 5) ps.push_back(i);
    }
    for (int i = 0; i < N; i++) B[i] = 0;
    for (int i = 0; i < ps.size(); i++) B[ps[i]] = 11;
    playRound(B, R);
    for (int i = 0; i < N; i++) {
        if (R[i] == 12) return i;
    }
    return 0;
}

mt19937 rnd(time(NULL));

int greaterValue(int N, int W) {
    int B[100], R[100];
    for (int i = 0; i < 100; i++) B[i] = 0;
    int L = 1, RG = 9;
    while (L <= RG) {
        int M = (L + RG) / 2;
        B[0] = B[1] = M;
        playRound(B, R);
        if (R[0] > B[0] && R[1] > B[1]) L = M + 1;
        else if (R[0] <= B[0] && R[1] <= B[1]) RG = M -1;
        else {
            return (R[0] < R[1]);
        }
    }
    B[0] = B[1] = L;
    playRound(B, R);
    return R[0] < R[1];
}

struct xd {
    pair<int, int> vals_seg;
    vector<int> poss;
};

void allValues(int N, int W, int *P) {
    int B[100], R[100];
        vector<xd> lol;
        vector<int> ap(N);
        iota(all(ap), 0);
        lol.pb({{1, N}, ap});
        while (lol.size() < N) {
            //cout << "yep" << endl;
            vector<xd> new_lol;
            for (int i = 0; i < sz(lol); i++) {
                if (lol[i].poss.size() == 1) {
                    new_lol.pb(lol[i]);
                    continue;
                }
                int l = lol[i].vals_seg.first, r = lol[i].vals_seg.second;
                int sm = 0;
                for (int j = l; j <= r; j++) sm += j;
                bool good = false;
                pair<int, int> cs;
                for (int cost = 1; cost * (r - l + 1) <= W; cost++) {
                    if (good) break;
                    for (int c2 = 0; c2 * (l - 1) + cost * (r - l + 1) <= W && (l != 1 || c2 <= 0); c2++) {
                        if (good) break;
                        int cntif0 = min(l - 1, (W - (N - r)) / (c2 + 1));
                        int cntifall = min(l - 1, max(0, ((W - (N - r)) - (cost + 1) * (r - l + 1)) / (c2 + 1)));
                        int currans = max((2 * l - 1 - cntif0) * cntif0 / 2, sm + (2 * l - 1 - cntifall) * cntifall / 2);
                        if ((r - l + 1) * (cost + 1) + N - r > W) {
                            currans = (2 * l - 1 - cntif0) * cntif0 / 2;
                        }
                        for (int newcnt = 1; newcnt < r - l + 1; newcnt++) {
                            int curcnt = min(l - 1, max(0, ((W - (N - r)) - newcnt * (cost + 1)) / (c2 + 1)));
                            if (currans < (2 * r - newcnt + 1) * newcnt / 2 + (2 * l - 1 - curcnt) * curcnt / 2) {
                                cs = {cost, c2};
                                good = true;
                                break;
                            }
                        }   
                    }
                }

                for (int j = 0; j < 100; j++) {
                    B[j] = 0;
                }
                for (int j = 0; j < i; j++) {
                    for (int pos : lol[j].poss) B[pos] = cs.second;
                }
                for (int pos : lol[i].poss) B[pos] = cs.first;
                playRound(B, R);

                vector<int> highs, lows;
                for (int pos : lol[i].poss) {
                    if (R[pos] > B[pos]) highs.pb(pos);
                    else lows.pb(pos);
                }
                new_lol.pb({{lol[i].vals_seg.first, lol[i].vals_seg.first + lows.size() - 1}, lows});
                new_lol.pb({{lol[i].vals_seg.first + lows.size(), lol[i].vals_seg.second}, highs});
            }   
            swap(new_lol, lol);
        }

        for (int i = 0; i < N; i++) {
            P[lol[i].poss[0]] = i + 1;
        }
}

Compilation message (stderr)

koala.cpp: In function 'int maxValue(int, int)':
koala.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < ps.size(); i++) B[ps[i]] = 11;
      |                     ~~^~~~~~~~~~~
koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:86:27: warning: comparison of integer expressions of different signedness: 'std::vector<xd>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |         while (lol.size() < N) {
      |                ~~~~~~~~~~~^~~

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