제출 #568489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568489		hollwo_pelw	코알라 (APIO17_koala)	C++17	90 / 100	46 ms	720 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;
}

int dp[105][205], ct[105][205], need[105];

inline int get_p(int N, int W, int LL, int RR) {
	for (int p = 1; p <= W; p++) {
		memset(dp, 0, sizeof dp);
		memset(ct, 0, sizeof ct);

		fill(need + 1, need + N + 1, 1);
		for (int i = LL; i <= RR; i++)
			need[i] = p + 1;

		for (int i = 1; i <= N; i++) {
			for (int j = 0; j <= W; j++) {
				dp[i][j] = dp[i - 1][j];
				ct[i][j] = ct[i - 1][j];
				if (j >= need[i] && dp[i][j] < dp[i - 1][j - need[i]] + i) {
					dp[i][j] = dp[i - 1][j - need[i]] + i;
					ct[i][j] = ct[i - 1][j - need[i]] + (i <= RR && i >= LL);
				}
			}
		}

		if (ct[N][W] > 0 && ct[N][W] < RR - LL + 1)
			return p;
	}

	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;
	
	int f = get_p(W, W, LL, RR);

	__init__();
	for (int i : pos) B[i] = f;
	
	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();
	solve(LL, mid - 1, W, P, lef), solve(mid, 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: 0 / 10
• Subtask 5: 53 / 53