Submission #587471

#	Time	Username	Problem	Language	Result	Execution time	Memory
587471		Namnamseo	Koala Game (APIO17_koala)	C++17	37 / 100	50 ms	336 KiB

koala

#include "koala.h"
#include <algorithm>
#include <vector>
#include <numeric>
using namespace std;
using vi=vector<int>;

vi Play(vi q) {
	vi ret(q.size());
	playRound(q.data(), ret.data());
	return ret;
}

int minValue(int N, int W) {
	vi v(N);
	v[0] = 1;
	vi res = Play(v);
	if (res[0] >= 1) res[0] -= 1;
	for (int i=0; i<N; ++i) if (!res[i]) return i;
    return 0;
}

int maxValue(int N, int W) {
	vi larger(N);
	iota(larger.begin(), larger.end(), 0);
	while (larger.size() > 1u) {
		vi mask(N);
		int afford = W / larger.size();
		for (int i:larger) mask[i] = afford;

		auto res = Play(mask);
		vi larger_new;
		for (int i:larger) if (res[i]) larger_new.push_back(i);
		larger = larger_new;
	}
    return larger[0];
}

int greaterValue(int N, int W) {
	int l = 0, r = 15;
	vi q(N);
	for (;;) {
		int m = (l+r)/2;
		q[0] = q[1] = m;
		vi res = Play(q);

		if (res[0] != res[1]) {
			return res[0] < res[1];
		}

		if (!res[0]) r = m;
		else l = m;
	}
    return 0;
}

void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        vi buf(N);

        fill(buf.begin(), buf.end(), 2);
        vi tmp = Play(buf);

        vi large, small;
        for (int i=0; i<N; ++i) {
            if (tmp[i] > 2) {
                large.push_back(i);
            } else {
                small.push_back(i);
            }
        }

        fill(buf.begin(), buf.end(), 0);
        auto Sort = [&](vi &v) {
            sort(v.begin(), v.end(), [&](const int& a, const int& b) {
                buf[a] = buf[b] = 100;
                tmp = Play(buf);
                buf[a] = buf[b] = 0;

                return tmp[a] < tmp[b];
            });
        };
        Sort(small);
        Sort(large);

        int ss = small.size();
        for (int i=0; i<ss; ++i) P[small[i]] = 1+i;
        for (int i=0; i<(N-ss); ++i) P[large[i]] = 1+ss+i;

    } else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    }
}

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