Submission #544906

#	Time	Username	Problem	Language	Result	Execution time	Memory
544906		amunduzbaev	Koala Game (APIO17_koala)	C++17	96 / 100	72 ms	344 KiB

koala

#include "koala.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

int minValue(int N, int W) {
	int B[N] {}, R[N] {};
	B[0] = 1;
	playRound(B, R);
	for(int i=0;i<N;i++){
		if(R[i] > B[i]) continue;
		else return i;
	} assert(false);
    // TODO: Implement Subtask 1 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    return 0;
}

int maxValue(int N, int W) {
	vector<int> p(N);
	for(int i=0;i<N;i++) p[i] = i;
	while((int)p.size() > 1){
		int v = W / (int)p.size();
		int B[N] {}, R[N] {};
		for(auto x : p) B[x] = v;
		playRound(B, R);
		vector<int> t;
		for(auto x : p){
			if(B[x] < R[x]){
				t.push_back(x);
			}
		}
		
		swap(p, t);
	}
	
	assert((int)p.size() == 1);
	return p[0];
    // TODO: Implement Subtask 2 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    return 0;
}

int greaterValue(int N, int W) {
	int is = -1;
	auto ask = [&](int v){
		int B[N] {}, R[N] {};
		B[0] = B[1] = v;
		playRound(B, R);
		int c = (R[0] > B[0]) + (R[1] > B[1]);
		if(c == 1){
			if(R[0] > B[0]) is = 0;
			else is = 1;
		} return c;
	};
	
	int l = 1, r = 8;
	while(l < r){
		int m = (l + r) >> 1;
		int v = ask(m);
		if(v == 1) break;
		if(v == 2) l = m + 1;
		else r = m - 1;
	}
	
	if(~is) return is;
	assert(l == r);
	ask(l);
	return is;
	
    // TODO: Implement Subtask 3 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    return 0;
}

#define ar array

void allValues(int N, int W, int *P) {
	vector<int> pref(N + 1);
	for(int i=1;i<=N;i++){
		pref[i] = pref[i-1] + i;
	}
	
	auto check = [&](int l, int r, int v){
		ar<int, 2> mx {-1, -1};
		int lef = W - (N - r);
		for(int x=0;x<=(r - l + 1);x++){
			if(x * (v + 1) > lef) break;
			int res = pref[N] - pref[r];
			res += (pref[r] - pref[r - x]);
			int rem = lef - x * (v + 1);
			res += (pref[l - 1] - pref[max(0, l - 1 - rem)]);
			if(mx[0] < res) mx = {res, x};
			//~ mx = max(mx, {res, x});
		}
		
		assert(~mx[1]);
		return mx[1];
	};
	
	auto ask = [&](vector<int> p, int v) -> ar<vector<int>, 2>{
		int B[N] {}, R[N] {};
		for(auto x : p) B[x] += v;
		playRound(B, R);
		ar<vector<int>, 2> t;
		for(auto x : p){
			if(B[x] < R[x]) t[1].push_back(x);
			else t[0].push_back(x);
		} return t;
	};
	
	int cnt = 0;
	
	function<void(int, int, vector<int>)> go = [&](int l, int r, vector<int> p){
		assert(r - l + 1 == (int)p.size());
		if(l == r){
			assert((int)p.size() == 1);
			P[p[0]] = l;
			return;
		}
		
		int h = (r - l + 1) >> 1;
		int lx = 1, rx = (W - N + r) / (r - l + 1);
		while(lx < rx){
			int m = (lx + rx) >> 1;
			int y = check(l, r, m);
			if(y <= h) rx = m;
			else lx = m + 1;
		}
		
		if(lx > 1){
			int y1 = check(l, r, lx);
			int y2 = check(l, r, lx - 1);
			if(abs(y1 - h) <= abs(y2 - h)){
				ar<vector<int>, 2> t = ask(p, lx);
				//~ assert(y1 == (int)t[1].size());
				int m = r - y1; cnt++;
				go(l, m, t[0]);
				go(m + 1, r, t[1]);
			} else {
				ar<vector<int>, 2> t = ask(p, lx + 1);
				//~ assert(y2 == (int)t[1].size());
				int m = r - y2; cnt++;
				go(l, m, t[0]);
				go(m + 1, r, t[1]);
			}
		} else {
			ar<vector<int>, 2> t = ask(p, lx);
			int y = check(l, r, lx);
			//~ assert(y == (int)t[1].size());
			int m = r - y; cnt++;
			go(l, m, t[0]);
			go(m + 1, r, t[1]);
		}
	};
	
	vector<int> p(N);
	iota(p.begin(), p.end(), 0);
	go(1, N, p);
}

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