Submission #97228

#	Time	Username	Problem	Language	Result	Execution time	Memory
97228		E869120	Koala Game (APIO17_koala)	C++14	47 / 100	79 ms	512 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 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 {
        
    }
}

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++; }
            ~~~^~~~~~~~~~~~

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