| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 286591 | AaronNaidu | Scales (IOI15_scales) | C++14 | 0 ms | 0 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.
#include <bits/stdc++.h>
#include "scales.h"
using namespace std;
vector<vector<int> > poss;
bool used[7];
int aCount, bCount, cCount;
void init(int T) {}
int vectorFind(vector<int> v, int a) {
for (int i = 0; i < v.size(); i++) {
if (v[i] == a) return i;
}
return -1;
}
void generatePerms(vector<int> v) {
if (v.size() == 6) {
poss.push_back(v);
return;
}
for (int i = 1; i <= 6; i++) {
if (!used[i]) {
used[i] = true;
v.push_back(i);
generatePerms(v);
v.pop_back();
used[i] = false;
}
}
}
int checkMin(int a, int b, int c) {
aCount = bCount = cCount = 0;
for (auto i : poss) {
if (vectorFind(i, a) < vectorFind(i, b) and vectorFind(i, a) < vectorFind(i, c)) {
aCount++;
}
else if (vectorFind(i, b) < vectorFind(i,c)) {
bCount++;
}
else {
cCount++;
}
}
return max(aCount, max(bCount, cCount));
}
int checkMax(int a, int b, int c) {
aCount = bCount = cCount = 0;
for (auto i : poss) {
if (vectorFind(i, a) > vectorFind(i, b) and vectorFind(i, a) > vectorFind(i, c)) {
aCount++;
}
else if (vectorFind(i, b) > vectorFind(i,c)) bCount++;
else cCount++;
}
return max(aCount, max(bCount, cCount));
}
int checkMed(int a, int b, int c) {
aCount = bCount = cCount = 0;
for (auto i : poss) {
if (vectorFind(i, b) < vectorFind(i, a) and vectorFind(i, a) < vectorFind(i, c)) aCount++;
else if (vectorFind(i, c) < vectorFind(i,a) and vectorFind(i, a) < vectorFind(i, b)) aCount++;
else if (vectorFind(i, c) < vectorFind(i,b) and vectorFind(i, b) < vectorFind(i, a)) bCount++;
else if (vectorFind(i, a) < vectorFind(i,b) and vectorFind(i, b) < vectorFind(i, c)) bCount++;
else cCount++;
}
return max(aCount, max(bCount, cCount));
}
int checkOther(int a, int b, int c, int d) {
aCount = bCount = cCount = 0;
for (auto i : poss)
{
vector<pair<int, int> > tests;
tests.push_back({vectorFind(i, a), 1});
tests.push_back({vectorFind(i, b), 2});
tests.push_back({vectorFind(i, c), 3});
tests.push_back({vectorFind(i, d), 4});
sort(tests.begin(), tests.end());
if (tests[0].second == 4)
{
if (tests[1].second == 1) aCount++;
if (tests[1].second == 2) bCount++;
if (tests[1].second == 3) cCount++;
}
if (tests[1].second == 4)
{
if (tests[2].second == 1) aCount++;
if (tests[2].second == 2) bCount++;
if (tests[2].second == 3) cCount++;
}
if (tests[2].second == 4)
{
if (tests[3].second == 1) aCount++;
if (tests[3].second == 2) bCount++;
if (tests[3].second == 3) cCount++;
}
if (tests[3].second == 4)
{
if (tests[0].second == 1) aCount++;
if (tests[0].second == 2) bCount++;
if (tests[0].second == 3) cCount++;
}
}
return max(max(aCount, bCount), cCount);
}
void optimalQuestion() {
int minAnswer = 1000000000;
int minType = -1;
int mina, minb, minc, mind;
for (int i = 1; i <= 6; i++) {
for (int j = i+1; j <= 6; j++) {
for (int k = j+1; k <= 6; k++) {
int small = checkMin(i, j, k);
int large = checkMax(i, j, k);
int med = checkMed(i, j, k);
if (small < minAnswer) {
minAnswer = small;
mina = i;
minb = j;
minc = k;
minType = 1;
}
if (large < minAnswer) {
minAnswer = large;
mina = i;
minb = j;
minc = k;
minType = 3;
}
if (med < minAnswer) {
minAnswer = med;
mina = i;
minb = j;
minc = k;
minType = 2;
}
for (int l = k+1; l <= 6; l++) {
int ans;
ans = checkOther(i, j, k, l);
if (ans < minAnswer) {
minAnswer = ans;
mina = i;
minb = j;
minc = k;
mind = l;
minType = 4;
}
ans = checkOther(i, j, l, k);
if (ans < minAnswer) {
minAnswer = ans;
mina = i;
minb = j;
minc = l;
mind = k;
minType = 4;
}
ans = checkOther(i, k, l, j);
if (ans < minAnswer) {
minAnswer = ans;
mina = i;
minb = k;
minc = l;
mind = j;
minType = 4;
}
ans = checkOther(j, k, l, i);
if (ans < minAnswer) {
minAnswer = ans;
mina = j;
minb = k;
minc = l;
mind = i;
minType = 4;
}
}
}
}
}
if (minType == 1) {
int x = getLightest(mina, minb, minc);
vector<vector<int> > newPossiblePerms;
for (auto i : poss) {
if (vectorFind(i, x) > vectorFind(i, mina) or vectorFind(i, x) > vectorFind(i, minb) or vectorFind(i, x) > vectorFind(i, minc)) {
continue;
}
newPossiblePerms.push_back(i);
}
poss = newPossiblePerms;
newPossiblePerms.clear();
}
if (minType == 3) {
int x = getHeaviest(mina, minb, minc);
vector<vector<int> > newPossiblePerms;
for (auto i : poss) {
if (vectorFind(i, x) < vectorFind(i, mina) or vectorFind(i, x) < vectorFind(i, minb) or vectorFind(i, x) < vectorFind(i, minc)) {
continue;
}
newPossiblePerms.push_back(i);
}
possiblePerms = newPossiblePerms;
newPossiblePerms.clear();
}
if (minType == 2) {
int x = getMedian(mina, minb, minc);
vector<vector<int> > newPossiblePerms;
for (auto i : poss) {
if (vectorFind(i, minb) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, mina)) {
newPossiblePerms.push_back(i);
}
if (vectorFind(i, mina) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minb)) {
newPossiblePerms.push_back(i);
}
if (vectorFind(i, minb) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minc)) {
newPossiblePerms.push_back(i);
}
if (vectorFind(i, minc) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minb)) {
newPossiblePerms.push_back(i);
}
if (vectorFind(i, mina) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minc)) {
newPossiblePerms.push_back(i);
}
if (vectorFind(i, minc) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, mina)) {
newPossiblePerms.push_back(i);
}
}
poss = newPossiblePerms;
newPossiblePerms.clear();
}
if (minType == 4) {
int y = getNextLightest(mina, minb, minc, mind);
vector<vector<int> > newPossiblePerms;
for (auto i : poss) {
vector<pair<int, int> > tests;
tests.push_back({vectorFind(i, mina), mina});
tests.push_back({vectorFind(i, minb), minb});
tests.push_back({vectorFind(i, minc), minc});
tests.push_back({vectorFind(i, mind), mind});
sort(tests.begin(), tests.end());
if ((tests[0].second == mind and tests[1].second == y) or (tests[1].second == mind and tests[2].second == y) or (tests[2].second == mind and tests[3].second == y) or (tests[3].second == mind and tests[4].second == y)) {
newPossiblePerms.push_back(i);
}
}
poss = newPossiblePerms;
newPossiblePerms.clear();
}
return;
}
void orderCoins() {
poss.clear();
generatePerms({});
int x = getLightest(1, 2, 3);
vector<vector<int> > newPossiblePerms;
for (auto i : poss) {
if (vectorFind(i, x) > vectorFind(i, 1) or vectorFind(i, x) > vectorFind(i, 2) or vectorFind(i, x) > vectorFind(i, 3)) {
continue;
}
newPossiblePerms.push_back(i);
}
poss = newPossiblePerms;
newPossiblePerms.clear();
x = getLightest(4, 5, 6);
for (auto i : poss) {
if (vectorFind(i, x) > vectorFind(i, 4) or vectorFind(i, x) > vectorFind(i, 5) or vectorFind(i, x) > vectorFind(i, 6)) {
continue;
}
newPossiblePerms.push_back(i);
}
poss = newPossiblePerms;
newPossiblePerms.clear();
while (poss.size() > 1) {
optimalQuestion();
}
int finalAnswer[6];
for (int i = 0; i < 6; i++) {
finalAnswer[i] = poss[0][i];
}
answer(finalAnswer);
return;
}