제출 #568465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568465		hollwo_pelw	코알라 (APIO17_koala)	C++17	47 / 100	85 ms	1336 KiB

koala

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

#include "koala.h"

int R[105], B[105];

void __init__() { memset(R, 0, sizeof R); memset(B, 0, sizeof B); }

int minValue(int N, int W) {
	__init__();
	B[0] = 1;
	playRound(B, R);

	for (int i = 1; i < N; i++)
		if (!R[i]) return i;

	return 0;
}

int maxValue(int N, int W) {
	vector<int> res(N);
	iota(res.begin(), res.end(), 0);

	while ((int) res.size() > 1) {
		__init__();
		for (auto i : res)
			B[i] = W / res.size();
		playRound(B, R);

		int f = *max_element(R, R + N);
		
		res.clear();
		for (int i = 0; i < N; i++)
			if (R[i] == f) res.push_back(i);
	}

	return res[0];
}

int greaterValue(int N, int W) {
	int l = 0, r = sqrt(N * 2);
	while (l <= r) {
		int mid = (l + r) >> 1;
		
		__init__();
		B[0] = B[1] = mid;
		playRound(B, R);

		int c0 = R[0] > B[0], c1 = R[1] > B[1];

		if (c0 ^ c1) {
			if (c0) return 0;
			if (c1) return 1;
		}

		if (c0) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}

	return 0;
}

void solve(int LL, int RR, int W, int *P, vector<int> pos) {
	if (LL == RR) {
		assert((int) pos.size() == 1);
		return P[pos[0]] = LL, (void) 0;
	}
	vector<int> lef, rig;
	
	__init__();
	for (int i : pos)
		B[i] = W / pos.size();
	
	playRound(B, R);

	for (int i : pos) {
		if (R[i] > B[i])
			rig.push_back(i);
		else
			lef.push_back(i);
	}
	int mid = LL + lef.size() - 1;
	solve(LL, mid, W, P, lef), solve(mid + 1, RR, W, P, rig);
}

void allValues(int N, int W, int *P) {
	vector<int> pos(N);
	iota(pos.begin(), pos.end(), 0);

	if (W == 2*N) {
		solve(1, N, W, P, pos);
	} else {
		solve(1, N, W, P, pos);
	}
}

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