Submission #57869

#	Time	Username	Problem	Language	Result	Execution time	Memory
57869		E869120	Scales (IOI15_scales)	C++14	71.43 / 100	363 ms	964 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

scales

#include "scales.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;

// -----------------------------

/*int Weight[7], Queries = 0;

int getLightest(int A, int B, int C) {
	Queries++;
	if (A <= 0 || A >= 7 || B <= 0 || B >= 7 || C <= 0 || C >= 7 || A == B || B == C || C == A) cout << "Wrong Answer [1]" << endl;
	vector<pair<int, int>>V;
	for (int i = 1; i <= 6; i++) {
		if (Weight[i] == A) V.push_back(make_pair(i, A));
		if (Weight[i] == B) V.push_back(make_pair(i, B));
		if (Weight[i] == C) V.push_back(make_pair(i, C));
	}
	sort(V.begin(), V.end());
	return V[0].second;
}
int getMedian(int A, int B, int C) {
	Queries++;
	if (A <= 0 || A >= 7 || B <= 0 || B >= 7 || C <= 0 || C >= 7 || A == B || B == C || C == A) cout << "Wrong Answer [2]" << endl;
	vector<pair<int, int>>V;
	for (int i = 1; i <= 6; i++) {
		if (Weight[i] == A) V.push_back(make_pair(i, A));
		if (Weight[i] == B) V.push_back(make_pair(i, B));
		if (Weight[i] == C) V.push_back(make_pair(i, C));
	}
	sort(V.begin(), V.end());
	return V[1].second;
}
int getHeaviest(int A, int B, int C) {
	Queries++;
	if (A <= 0 || A >= 7 || B <= 0 || B >= 7 || C <= 0 || C >= 7 || A == B || B == C || C == A) cout << "Wrong Answer [3]" << endl;
	vector<pair<int, int>>V;
	for (int i = 1; i <= 6; i++) {
		if (Weight[i] == A) V.push_back(make_pair(i, A));
		if (Weight[i] == B) V.push_back(make_pair(i, B));
		if (Weight[i] == C) V.push_back(make_pair(i, C));
	}
	sort(V.begin(), V.end());
	return V[2].second;
}
int getNextLightest(int A, int B, int C, int D) {
	Queries++;
	if (A <= 0 || A >= 7 || B <= 0 || B >= 7 || C <= 0 || C >= 7 || A == B || B == C || C == A) cout << "Wrong Answer [3]" << endl;
	vector<pair<int, int>>V; int S = 0;
	for (int i = 1; i <= 6; i++) {
		if (Weight[i] == A) V.push_back(make_pair(i, A));
		if (Weight[i] == B) V.push_back(make_pair(i, B));
		if (Weight[i] == C) V.push_back(make_pair(i, C));
		if (Weight[i] == D) S = i;
	}
	sort(V.begin(), V.end());
	for (int i = 0; i < V.size(); i++) {
		if (V[i].first > S) return V[i].second;
	}
	return V[0].second;
}
void answer(int W[]) {
	for (int i = 0; i < 6; i++) {
		if (W[i] != Weight[i + 1]) { cout << "Wrong Answer [4]" << endl; return; }
	}
	cout << "Accepted : Total Number of Queries = " << Queries << endl;
}*/

// -----------------------------

// ---------------------------------- 準備用クエリ ---------------------------------------

int WWW[7];

int _getLightest(int A, int B, int C) {
	if (A <= 0 || A >= 7 || B <= 0 || B >= 7 || C <= 0 || C >= 7 || A == B || B == C || C == A) cout << "Wrong Answer [1B]" << endl;
	vector<pair<int, int>>V;
	for (int i = 1; i <= 6; i++) {
		if (WWW[i] == A) V.push_back(make_pair(i, A));
		if (WWW[i] == B) V.push_back(make_pair(i, B));
		if (WWW[i] == C) V.push_back(make_pair(i, C));
	}
	sort(V.begin(), V.end());
	return V[0].second;
}
int _getMedian(int A, int B, int C) {
	if (A <= 0 || A >= 7 || B <= 0 || B >= 7 || C <= 0 || C >= 7 || A == B || B == C || C == A) cout << "Wrong Answer [2B]" << endl;
	vector<pair<int, int>>V;
	for (int i = 1; i <= 6; i++) {
		if (WWW[i] == A) V.push_back(make_pair(i, A));
		if (WWW[i] == B) V.push_back(make_pair(i, B));
		if (WWW[i] == C) V.push_back(make_pair(i, C));
	}
	sort(V.begin(), V.end());
	return V[1].second;
}
int _getHeaviest(int A, int B, int C) {
	if (A <= 0 || A >= 7 || B <= 0 || B >= 7 || C <= 0 || C >= 7 || A == B || B == C || C == A) cout << "Wrong Answer [3B]" << endl;
	vector<pair<int, int>>V;
	for (int i = 1; i <= 6; i++) {
		if (WWW[i] == A) V.push_back(make_pair(i, A));
		if (WWW[i] == B) V.push_back(make_pair(i, B));
		if (WWW[i] == C) V.push_back(make_pair(i, C));
	}
	sort(V.begin(), V.end());
	return V[2].second;
}
int _getNextLightest(int A, int B, int C, int D) {
	if (A <= 0 || A >= 7 || B <= 0 || B >= 7 || C <= 0 || C >= 7 || A == B || B == C || C == A) cout << "Wrong Answer [5B]" << endl;
	vector<pair<int, int>>V; int S = 0;
	for (int i = 1; i <= 6; i++) {
		if (WWW[i] == A) V.push_back(make_pair(i, A));
		if (WWW[i] == B) V.push_back(make_pair(i, B));
		if (WWW[i] == C) V.push_back(make_pair(i, C));
		if (WWW[i] == D) S = i;
	}
	sort(V.begin(), V.end());
	for (int i = 0; i < V.size(); i++) {
		if (V[i].first > S) return V[i].second;
	}
	return V[0].second;
}

// ---------------------------------- 準備用クエリ終了 -----------------------------------

void init(int T) {

}

struct State {
	int a[6];
};

void orderCoins() {
	vector<State>U;
	int p[6] = { 1,2,3,4,5,6 };
	do {
		State Y; for (int i = 0; i < 6; i++) Y.a[i] = p[i];
		U.push_back(Y);
	} while (next_permutation(p, p + 6));

	while (U.size() >= 2) {
		tuple<int, int, int, int>V; int maxn = 1000;
		for (int i = 1; i <= 6; i++) {
			for (int j = i + 1; j <= 6; j++) {
				for (int k = j + 1; k <= 6; k++) {
					int c1[6] = { 0,0,0,0,0,0 }, c2[6] = { 0,0,0,0,0,0 }, c3[6] = { 0,0,0,0,0,0 };
					for (State x : U) {
						for (int l = 0; l < 6; l++) WWW[l + 1] = x.a[l];
						c1[_getLightest(i, j, k) - 1]++;
						c2[_getMedian(i, j, k) - 1]++;
						c3[_getHeaviest(i, j, k) - 1]++;
					}
					int maxn1 = 0, maxn2 = 0, maxn3 = 0;
					for (int l = 0; l < 6; l++) maxn1 = max(maxn1, c1[l]);
					for (int l = 0; l < 6; l++) maxn2 = max(maxn2, c2[l]);
					for (int l = 0; l < 6; l++) maxn3 = max(maxn3, c3[l]);

					if (maxn1 < maxn) { maxn = maxn1; V = make_tuple(-1, i, j, k); }
					if (maxn2 < maxn) { maxn = maxn2; V = make_tuple(-2, i, j, k); }
					if (maxn3 < maxn) { maxn = maxn3; V = make_tuple(-3, i, j, k); }
				}
			}
		}
		if (get<0>(V) == -1) {
			int Z = getLightest(get<1>(V), get<2>(V), get<3>(V));
			vector<State>US;
			for (State x : U) {
				for (int i = 0; i < 6; i++) WWW[i + 1] = x.a[i];
				int F = _getLightest(get<1>(V), get<2>(V), get<3>(V));
				if (F == Z) US.push_back(x);
			}
			U = US;
		}
		if (get<0>(V) == -2) {
			int Z = getMedian(get<1>(V), get<2>(V), get<3>(V));
			vector<State>US;
			for (State x : U) {
				for (int i = 0; i < 6; i++) WWW[i + 1] = x.a[i];
				int F = _getMedian(get<1>(V), get<2>(V), get<3>(V));
				if (F == Z) US.push_back(x);
			}
			U = US;
		}
		if (get<0>(V) == -3) {
			int Z = getHeaviest(get<1>(V), get<2>(V), get<3>(V));
			vector<State>US;
			for (State x : U) {
				for (int i = 0; i < 6; i++) WWW[i + 1] = x.a[i];
				int F = _getHeaviest(get<1>(V), get<2>(V), get<3>(V));
				if (F == Z) US.push_back(x);
			}
			U = US;
		}
	}

	int WW[6]; for (int i = 0; i < 6; i++) WW[i] = U[0].a[i];
	answer(WW);
}

Compilation message (stderr)

In file included from grader.c:2:0:
graderlib.c: In function 'void answer(int*)':
graderlib.c:53:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (_ghksjhdfkae19ga_ > 1) 
     ^~
graderlib.c:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  for (i = 0; i < 6; i++) {
  ^~~
scales.cpp: In function 'int _getNextLightest(int, int, int, int)':
scales.cpp:120:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) {
                  ~~^~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:128:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^

Subtask 171.428571 / 100

#	Verdict	Execution time	Memory	Grader output
Fetching results...