Submission #107094

#	Time	Username	Problem	Language	Result	Execution time	Memory
107094		Noam527	Koala Game (APIO17_koala)	C++17	96 / 100	78 ms	512 KiB

koala

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 1;
const int OOO = 1;
using namespace std;

// returns such i that we get [i, r], [l, i - 1]
int put(int l, int r, int x = -1) {
	const int n = 100;
	if (x == -1) {
		x = n / (r - l + 1);
	}
	int at = r + 1, cost = 0, sum = 0, cnt = 0;
	int best = r + 1;
	pair<int, int> mx = { -1, -1 };
	while (at > l && cost + x + 1 <= n) {
		at--;
		sum += at;
		cnt++;
		cost += x + 1;
	}
	vector<int> other;
	for (int i = n; i >= 1; i--) {
		if (i < l || r < i) other.push_back(i);
	}
	int pos = -1;
	while (pos + 1 < other.size() && cost < n) {
		pos++;
		cost++;
		cnt++;
		sum += other[pos];
	}
	if (mx < make_pair(sum, cnt))
		mx = { sum, cnt }, best = at;

	while (at <= r) {
		cost -= x + 1;
		sum -= at;
		cnt--;
		at++;
		while (pos + 1 < other.size() && cost < n) {
			pos++;
			cost++;
			cnt++;
			sum += other[pos];
		}
		if (mx < make_pair(sum, cnt))
			mx = { sum, cnt }, best = at;
	}
	return best;
}

int nn;
void playRound(int *B, int *R);
/*
void playRound(int *B, int *R) {
	cout << "B: ";
	for (int i = 0; i < nn; i++) cout << B[i] << " "; cout << '\n';
	cout << "R: ";
	for (int i = 0; i < nn; i++) cin >> R[i];
}
*/
int B[105], R[105];

void clear() {
	for (int i = 0; i < nn; i++) B[i] = 0;
}
void play() {
	playRound(B, R);
}
vector<int> atleast(int k) {
	vector<int> rtn;
	for (int i = 0; i < nn; i++)
		if (R[i] >= k) rtn.push_back(i);
	return rtn;
}
vector<int> atmost(int k) {
	vector<int> rtn;
	for (int i = 0; i < nn; i++)
		if (R[i] <= k) rtn.push_back(i);
	return rtn;
}

int minValue(int n, int w) {
	nn = n;
	clear();
	B[0] = 1;
	play();
	
	vector<int> pos = atmost(0);
	if (pos.size()) return pos[0];
	return 0;
}

int maxValue(int n, int w) {
	nn = n;
	vector<int> prev, cur;
	for (int i = 0; i < n; i++) prev.push_back(i);
	while (prev.size() > 1) {
		clear();
		int val = n / int(prev.size());
		for (const auto &i : prev) B[i] = val;
		play();

		cur = atleast(1 + val);
		vector<int> cut;
		int p1 = 0, p2 = 0;
		while (p1 < prev.size() && p2 < cur.size()) {
			if (prev[p1] == cur[p2]) cut.push_back(prev[p1]), p1++, p2++;
			else if (prev[p1] < cur[p2]) p1++;
			else p2++;
		}
		prev = cut;
	}
	return prev[0];
}

int greaterValue(int n, int w) {
	nn = n;
	int lo = 1, hi = 8, mid;
	while (lo < hi) {
		mid = (lo + hi) / 2;
		clear();
		B[0] = B[1] = mid;
		play();
		if (R[0] > mid && R[1] > mid) lo = mid + 1;
		else if (R[0] <= mid && R[1] <= mid) hi = mid - 1;
		else {
			if (R[0] > mid) return 0;
			return 1;
		}
	}
	clear();
	B[0] = B[1] = lo;
	play();
	if (R[0] > lo) return 0;
	return 1;
}

bool cmp(int x, int y) {
	clear();
	B[x] = B[y] = 100;
	play();
	if (R[x] > 100) return false;
	return true;
}

int arr1[105], arr2[105];

void mergesort(vector<int> &a, int l, int r) {
	if (l >= r) return;
	int mid = (l + r) / 2;
	mergesort(a, l, mid);
	mergesort(a, mid + 1, r);
	int sz1 = 0, sz2 = 0, p1 = 0, p2 = 0;
	for (int i = l; i <= mid; i++)
		arr1[sz1++] = a[i];
	for (int i = mid + 1; i <= r; i++)
		arr2[sz2++] = a[i];
	while (p1 < sz1 && p2 < sz2) {
		if (cmp(arr1[p1], arr2[p2])) a[l + p1 + p2] = arr1[p1], p1++;
		else a[l + p1 + p2] = arr2[p2], p2++;
	}
	while (p1 < sz1)
		a[l + p1 + p2] = arr1[p1], p1++;
	while (p2 < sz2)
		a[l + p1 + p2] = arr2[p2], p2++;
}

int ans[105];

void calc(int l, int r, vector<int> pos) {
	if (l == r) {
		ans[pos[0]] = l;
		return;
	}
	int val = 1;
	while (put(l, r, val) == l) val++;
	clear();
	for (const auto &i : pos) B[i] = val;
	play();
	vector<int> small, big;
	for (const auto &i : pos)
		if (R[i] > val)
			big.push_back(i);
		else
			small.push_back(i);
	calc(l, l + (int)small.size() - 1, small);
	calc(l + (int)small.size(), r, big);
}

void allValues(int n, int w, int *P) {
	nn = n;
	if (w == 2 * n) {
		vector<int> p;
		for (int i = 0; i < n; i++) p.push_back(i);
		mergesort(p, 0, n - 1);
		for (int i = 0; i < n; i++)
			P[p[i]] = 1 + i;
		return;
	}
	else {
		vector<int> pos;
		for (int i = 0; i < n; i++) pos.push_back(i);
		calc(1, n, pos);
		for (int i = 0; i < n; i++) P[i] = ans[i];
	}
}
/*
int main() {
	int n;
	cin >> n;
	int res[105];
	allValues(n, n, res);
	cout << "the answer\n";
	for (int i = 0; i < n; i++) cout << res[i] << " "; cout << '\n';
}
*/

Compilation message (stderr)

koala.cpp: In function 'int put(int, int, int)':
koala.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (pos + 1 < other.size() && cost < n) {
         ~~~~~~~~^~~~~~~~~~~~~~
koala.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (pos + 1 < other.size() && cost < n) {
          ~~~~~~~~^~~~~~~~~~~~~~
koala.cpp: In function 'int maxValue(int, int)':
koala.cpp:113:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (p1 < prev.size() && p2 < cur.size()) {
          ~~~^~~~~~~~~~~~~
koala.cpp:113:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (p1 < prev.size() && p2 < cur.size()) {
                              ~~~^~~~~~~~~~~~

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