Submission #129179

#	Time	Username	Problem	Language	Result	Execution time	Memory
129179		keko37	Koala Game (APIO17_koala)	C++14	100 / 100	82 ms	984 KiB

koala

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

using namespace std;

const int MAXN = 105;

int n, w, flg;
int dp[105][105];
int B[MAXN], R[MAXN];

bool f (int ll, int rr, int c) {
	vector <int> a, b;
	for (int i = n; i >= 1; i--) {
		if (ll <= i && i <= rr) {
			if (a.empty()) a.push_back(i); else a.push_back(a.back() + i);
		} else {
			if (b.empty()) b.push_back(i); else b.push_back(b.back() + i);
		}
	}
	vector < pair <int, int> > res;
	int mx = -1;
	for (int i=0; i<=a.size(); i++) {
		for (int j=0; j<=b.size(); j++) {
			int cost = i * (c + 1) + j;
			int val = 0;
			if (i > 0) val += a[i-1];
			if (j > 0) val += b[j-1];
			if (cost <= w) {
				if (val > mx) {
					mx = val;
					res.clear();
					res.push_back(make_pair(i, j));
				} else if (val == mx) {
					res.push_back(make_pair(i, j));
				}
			}
		}
	}
	for (auto par : res) {
		if (par.first == 0 || par.first == a.size()) return 0;
	}
	return 1;
}

int calc (int ll, int rr) {
	int len = rr - ll + 1;
	int mx = w / len;
	for (int i = mx; i >= 1; i--) {
		if (f(ll, rr, i)) return i;
	}
	return -1;
}

void precompute () {
	for (int i=1; i<=n; i++) {
		for (int j=i+1; j<=n; j++) {
			dp[i][j] = calc(i, j);
		}
	}
}

vector <int> rjesi (int lo, int hi, vector <int> v) {
	if (lo == hi) return v;
	for (int i=0; i<n; i++) {
		B[i] = R[i] = 0;
	}
	for (auto x : v) {
		B[x] = dp[lo][hi];
	}
	playRound(B, R);
	vector <int> lef, rig;
	for (auto x : v) {
		if (R[x] > B[x]) rig.push_back(x); else lef.push_back(x);
	}
	if (flg == 0) lef = rjesi(lo, lo + lef.size() - 1, lef);
	rig = rjesi(lo + lef.size(), hi, rig);
	if (flg) return rig;
	for (auto x : rig) lef.push_back(x);
	return lef;
}

int minValue(int N, int W) {
	n = N; w = W;
	for (int i=0; i<n; i++) {
		B[i] = R[i] = 0;
	}
	B[0] = 1;
	playRound(B, R);
	for (int i=0; i<n; i++) {
		if (R[i] == 0) return i;
	}
}

int maxValue(int N, int W) {
	n = N; w = W;
	if (flg == 0) precompute();
	flg++;
	vector <int> sol;
	for (int i=0; i<n; i++) sol.push_back(i);
    return rjesi(1, n, sol).back();
}

int greaterValue(int N, int W) {
	n = N; w = W;
	int lo = 1, hi = min(W / 2, 9);
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		for (int i=0; i<n; i++) {
			B[i] = R[i] = 0;
		}
		B[0] = B[1] = mid;
		playRound(B, R);
		bool ok0 = R[0] > B[0];
		bool ok1 = R[1] > B[1];
		if (ok0 == ok1) {
			if (ok0 == 1) {
				lo = mid + 1;
			} else {
				hi = mid - 1;
			}
		} else {
			if (ok0) return 0;
			return 1;
		}
	}
}

void allValues(int N, int W, int *P) {
	n = N; w = W;
	precompute();
	vector <int> sol;
	for (int i=0; i<n; i++) sol.push_back(i);
	sol = rjesi(1, n, sol);
	for (int i=0; i<N; i++) {
		P[sol[i]] = i + 1;
	}
}

Compilation message (stderr)

koala.cpp: In function 'bool f(int, int, int)':
koala.cpp:23:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<=a.size(); i++) {
                ~^~~~~~~~~~
koala.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<=b.size(); j++) {
                 ~^~~~~~~~~~
koala.cpp:41:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (par.first == 0 || par.first == a.size()) return 0;
                         ~~~~~~~~~~^~~~~~~~~~~
koala.cpp: In function 'int minValue(int, int)':
koala.cpp:93:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:127:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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