Submission #166376

#	Time	Username	Problem	Language	Result	Execution time	Memory
166376		qkxwsm	Koala Game (APIO17_koala)	C++14	75 / 100	71 ms	584 KiB

koala

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

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

random_device rd;
mt19937 rng(rd());

template<class T>
T randomize(T mod)
{
	return uniform_int_distribution<T>(0, mod - 1)(rng);
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= b; i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) x.begin(), x.end()
#define INF 1000000007
#define LLINF 2696969696969696969

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, Q;
vi arr, rec;
vi test = {8, 4, 2, 1};
vi ans;

vi ask(vi s)
{
	int tmp[100], tmp1[100];
	FOR(i, 0, N)
	{
		tmp[i] = s[i];
	}
	playRound(tmp, tmp1);
	FOR(i, 0, N)
	{
		s[i] = tmp1[i];
	}
	return s;
}

int minValue(int n, int q)
{
	N = n; Q = q; arr.resize(N);
	arr[0] = 1;
	rec = ask(arr);
	FOR(i, 1, N)
	{
		if (rec[i] == 0) return i;
	}
    return 0;
}

int maxValue(int n, int q)
{
    N = n; Q = q; arr.resize(N);
	vi cands;
	FOR(i, 0, N) cands.PB(i);
	while(SZ(cands) > 1)
	{
		vi tmp;
		FOR(i, 0, N) arr[i] = 0;
		for (int x : cands) arr[x] = N / SZ(cands);
		rec = ask(arr);
		FOR(i, 0, N)
		{
			if (rec[i] > (N / SZ(cands))) tmp.PB(i);
		}
		cands = tmp;
		// for (int x : cands)
		// {
		// 	cerr << x << ' ';
		// }
		// cerr << endl;
	}
	return cands[0];
}

bool cmp2(int i, int j)
{
	if (i == j) return false;
	FOR(k, 0, N) arr[k] = 0;
	int lo = 1, hi = 9;
	while(true)
	{
		int mid = (hi + lo) >> 1;
		arr[i] = mid; arr[j] = mid;
		rec = ask(arr);
		if (rec[i] > mid && rec[j] <= mid) return false;
		if (rec[i] <= mid && rec[j] > mid) return true;
		if (rec[i] > mid && rec[j] > mid) lo = mid + 1;
		else hi = mid - 1;
	}
	// return false;
}
bool cmp(int i, int j)
{
	if (i == j) return false;
	//is i < j?
	FOR(k, 0, N) arr[k] = 0;
	for (int x : test)
	{
		arr[i] = x; arr[j] = x;
		rec = ask(arr);
		if (rec[i] > x && rec[j] <= x) return false;
		if (rec[i] <= x && rec[j] > x) return true;
	}
	return false;
}

int greaterValue(int n, int q)
{
	N = n; Q = q; arr.resize(N);
	//say you put x on each.
	//they will put 98 on thhe other guys and 0 on both of you.
	//they will put 99-x on the other guys and x+1 on one of you. it's a sacrifice of 1+2+...x-1. for you. but the next one needs x....2x-2
	//they will put 98-2x on everybody else and x+1 on both of you.
	//they put it on the more expensive of you two.
	return cmp2(0, 1);
}

bool cmp1(int a, int b)
{
	//return true if a < b
	FOR(i, 0, N)
	{
		arr[i] = 0;
	}
	arr[a] = N; arr[b] = N;
	rec = ask(arr);
	return (rec[b] > N);
}
vi ord[300];
void build4(int w, int L, int R)
{
	ord[w].clear();
	if (L == R)
	{
		ord[w].PB(L);
		return;
	}
	int mid = (L + R) >> 1;
	build4(w << 1, L, mid);
	build4(w << 1 | 1, mid + 1, R);
}
void solve4(int w, int L, int R)
{
	if (L == R) return;
	int mid = (L + R) >> 1;
	solve4(w << 1, L, mid);
	solve4(w << 1 | 1, mid + 1, R);
	int lt = 0, rt = 0;
	while(lt < SZ(ord[w << 1]) || rt < SZ(ord[w << 1 | 1]))
	{
		if (rt == SZ(ord[w << 1 | 1]) || ((lt != SZ(ord[w << 1]) && cmp1(ord[w << 1][lt], ord[w << 1 | 1][rt]))))
		{
			ord[w].PB(ord[w << 1][lt]);
			lt++;
		}
		else
		{
			ord[w].PB(ord[w << 1 | 1][rt]);
			rt++;
		}
	}
}
void allValues(int n, int q, int *res)
{
    N = n; Q = q; arr.resize(N); ans.resize(N);
	if (Q == 2 * N)
	{
		build4(1, 0, N - 1);
		solve4(1, 0, N - 1);
		FOR(i, 0, SZ(ord[1]))
		{
			ans[ord[1][i]] = i + 1;
		}
	}
	else
	{
		FOR(i, 0, N) arr[i] = 1;
		rec = ask(arr);
		vi upper, lower;
		FOR(i, 0, N)
		{
			if (rec[i]) upper.PB(i);
			else lower.PB(i);
		}
		FOR(i, 0, SZ(upper))
		{
			swap(upper[i], upper[randomize(i + 1)]);
		}
		FOR(i, 0, SZ(lower))
		{
			swap(lower[i], lower[randomize(i + 1)]);
		}
		sort(ALL(upper), cmp);
		sort(ALL(lower), cmp2);
		ans = lower;
		ans.insert(ans.end(), ALL(upper));
		FOR(i, 0, N)
		{
			arr[ans[i]] = i + 1;
		}
		ans = arr;
	}
	//eh we only have N.
	//well you know who the upper half is now.
	FOR(i, 0, N) res[i] = ans[i];
	return;
}

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