Submission #97229

#	Time	Username	Problem	Language	Result	Execution time	Memory
97229		E869120	Koala Game (APIO17_koala)	C++14	100 / 100	81 ms	680 KiB

koala

#include "koala.h"
#include <iostream>
#include <vector>
using namespace std;

int D[109], R[109];

void preset() {
	for (int i = 0; i < 109; i++) { D[i] = 0; R[i] = 0; }
}

int minValue(int N, int W) {
	preset(); D[0] = 1;
	playRound(D, R);
	for (int i = 0; i < N; i++) {
		if (D[i] >= R[i]) return i;
	}
	return -1;
}

int maxValue(int N, int W) {
	int P[4] = { 1, 2, 4, 11 };
	vector<int>I; for (int i = 0; i < N; i++) I.push_back(i);
	for (int i = 0; i < 4; i++) {
		preset();
		for (int j = 0; j < I.size(); j++) D[I[j]] = P[i];
		playRound(D, R);
		vector<int>II; for (int j = 0; j < I.size(); j++) { if (D[I[j]] < R[I[j]]) II.push_back(I[j]); }
		I = II;
	}
	return I[0];
}

int solve_3(int N, int W, int P) {
	preset();
	D[0] = P; D[1] = P;
	playRound(D, R);
	int v1 = 0; if (D[0] < R[0]) v1 = 1;
	int v2 = 0; if (D[1] < R[1]) v2 = 2;
	return v1 + v2;
}

int greaterValue(int N, int W) {
	int G = solve_3(N, W, 6);
	if (G == 1 || G == 2) return G - 1;

	if (G == 0) {
		int G1 = solve_3(N, W, 1); if (G1 == 1 || G1 == 2) return G1 - 1;
		int G2 = solve_3(N, W, 3); if (G2 == 1 || G2 == 2) return G2 - 1;
		return -1;
	}
	if (G == 3) {
		int G1 = solve_3(N, W, 9); if (G1 == 1 || G1 == 2) return G1 - 1;
		return -1;
	}
	return -1;
}

bool isgreater(int N, int u, int v) {
	preset();
	D[u] = N; D[v] = N;
	playRound(D, R);

	if (R[v] > D[v]) {
		// u < v
		return true;
	}
	return false;
}

vector<int> mergesort(int N, vector<int>J) {
	if (J.size() == 1) return J;
	vector<int>J1, J2;
	for (int i = 0; i < J.size() / 2; i++) J1.push_back(J[i]);
	for (int i = J.size() / 2; i < J.size(); i++) J2.push_back(J[i]);

	vector<int>K1 = mergesort(N, J1);
	vector<int>K2 = mergesort(N, J2);
	vector<int>L; int cl = 0, cr = 0;
	while (cl + cr < (int)J.size()) {
		if (cl == J1.size()) { L.push_back(K2[cr]); cr++; }
		else if (cr == J2.size()) { L.push_back(K1[cl]); cl++; }
		else {
			bool t = isgreater(N, K1[cl], K2[cr]);
			if (t == true) { L.push_back(K1[cl]); cl++; }
			else { L.push_back(K2[cr]); cr++; }
		}
	}
	return L;
}

void playRound_virtual(int N, int W, int *B, int *R) {
	int i, j;
	int S = 0; for (i = 0; i < N; ++i) S += B[i];

	int cache[2][205];
	int num[2][205];
	char taken[105][205];

	for (i = 0; i < 205; ++i) { cache[1][i] = 0; num[1][i] = 0; }

	for (i = 0; i < N; ++i) {
		int v = B[i] + 1;
		int ii = i & 1;
		int o = ii ^ 1;
		for (j = 0; j <= W; ++j) {
			cache[ii][j] = cache[o][j];
			num[ii][j] = num[o][j];
			taken[i][j] = 0;
		}
		for (j = W; j >= v; --j) {
			int h = cache[o][j - v] + (i + 1);
			int hn = num[o][j - v] + 1;
			if (h > cache[ii][j] || (h == cache[ii][j] && hn > num[ii][j])) {
				cache[ii][j] = h;
				num[ii][j] = hn;
				taken[i][j] = 1;
			}
			else {
				taken[i][j] = 0;
			}
		}
	}

	int cur = W;
	for (i = N - 1; i >= 0; --i) {
		R[i] = taken[i][cur] ? (B[i] + 1) : 0;
		cur -= R[i];
	}
}

int find_optimal(int N, int W, int cl, int cr) {
	for (int i = 20; i >= 1; i--) {
		if (i*(cr - cl + 1) > W) continue;
		preset();
		for (int j = cl; j <= cr; j++) D[j] = i;
		playRound_virtual(N, W, D, R);
		for (int j = cl; j <= cr; j++) {
			if (D[j] < R[j]) return i;
		}
	}
	return -1;
}

int FinalAnswer[100];

void solve(int N, int W, int cl, int cr, vector<int>vec) {
	if (cl == cr) {
		FinalAnswer[vec[0]] = cl + 1;
		return;
	}
	int Z = find_optimal(N, W, cl, cr);
	preset();
	for (int j = 0; j < vec.size(); j++) D[vec[j]] = Z;
	playRound(D, R);

	vector<int>p1, p2;
	for (int j = 0; j < vec.size(); j++) {
		if (D[vec[j]] < R[vec[j]]) p2.push_back(vec[j]);
		else p1.push_back(vec[j]);
	}
	solve(N, W, cl, cl + p1.size() - 1, p1);
	solve(N, W, cl + p1.size(), cr, p2);
}

void allValues(int N, int W, int *P) {
    if (W == 2*N) {
		vector<int>K; for (int i = 0; i < N; i++) K.push_back(i);
		vector<int>KK = mergesort(N, K);
		for (int i = 0; i < N; i++) P[KK[i]] = i + 1;
    }
	else {
		vector<int>I; for (int j = 0; j < N; j++) I.push_back(j);
		solve(N, W, 0, N - 1, I);
		for (int i = 0; i < N; i++) P[i] = FinalAnswer[i];
    }
}

Compilation message (stderr)

koala.cpp: In function 'int maxValue(int, int)':
koala.cpp:26:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < I.size(); j++) D[I[j]] = P[i];
                   ~~^~~~~~~~~~
koala.cpp:28:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   vector<int>II; for (int j = 0; j < I.size(); j++) { if (D[I[j]] < R[I[j]]) II.push_back(I[j]); }
                                  ~~^~~~~~~~~~
koala.cpp: In function 'std::vector<int> mergesort(int, std::vector<int>)':
koala.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < J.size() / 2; i++) J1.push_back(J[i]);
                  ~~^~~~~~~~~~~~~~
koala.cpp:75:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = J.size() / 2; i < J.size(); i++) J2.push_back(J[i]);
                             ~~^~~~~~~~~~
koala.cpp:81:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (cl == J1.size()) { L.push_back(K2[cr]); cr++; }
       ~~~^~~~~~~~~~~~
koala.cpp:82:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if (cr == J2.size()) { L.push_back(K1[cl]); cl++; }
            ~~~^~~~~~~~~~~~
koala.cpp: In function 'void solve(int, int, int, int, std::vector<int>)':
koala.cpp:154:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < vec.size(); j++) D[vec[j]] = Z;
                  ~~^~~~~~~~~~~~
koala.cpp:158:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < vec.size(); j++) {
                  ~~^~~~~~~~~~~~

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