Submission #1076913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076913		Elias	Scales (IOI15_scales)	C++17	0 / 100	1092 ms	848 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

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#ifdef _DEBUG
void init(int T);
void orderCoins();
void answer(int C[]);

int getMedian(int A, int B, int C);
int getHeaviest(int A, int B, int C);
int getLightest(int A, int B, int C);
int getNextLightest(int A, int B, int C, int D);
#else
#include "scales.h"
#endif

int all[] = {1, 3, 9, 27, 81, 243, 729, 729, 729, 729};

int pow3(int i)
{
return all[i];
}

void init(int T) {}

int getNLghtest(vector<int> &ind, int A, int B, int C, int D)
{
int allLess = 1;

if (ind[A] > ind[D] || ind[B] > ind[D] || ind[C] > ind[D])
allLess = 0;

if (allLess == 1)
{
if (ind[A] < ind[B] && ind[A] < ind[C])
return A;

if (ind[B] < ind[A] && ind[B] < ind[C])
return B;

return C;
}

if (ind[A] > ind[D])
{
if ((ind[A] < ind[B] || ind[B] < ind[D]) &&
(ind[A] < ind[C] || ind[C] < ind[D]))
return A;
}

if (ind[B] > ind[D])
{
if ((ind[B] < ind[A] || ind[A] < ind[D]) &&
(ind[B] < ind[C] || ind[C] < ind[D]))
return B;
}

return C;
}

vector<int> result;

vector<int> solve(int depth, vector<vector<int>> possibilities, bool confirmed)
{
if (possibilities.size() == 0) {
assert(confirmed == false);
return {0};
}

if (possibilities.size() == 1)
{
if (confirmed)
return *possibilities.begin();
else
return {0};
}

if (depth == 0) {
assert(confirmed == false);
return {};
}


for (int a = 1; a <= 6; a++)
for (int b = a + 1; b <= 6; b++)
for (int c = b + 1; c <= 6; c++)
{
{
vector<vector<int>> partition_a;
vector<vector<int>> partition_b;
vector<vector<int>> partition_c;

for (auto poss : possibilities)
{
vector<int> ind(7);
for (int i = 0; i < 6; i++)
ind[poss[i]] = i;

if (ind[a] < ind[b] && ind[a] < ind[c])
partition_a.push_back(poss);
else if (ind[b] < ind[a] && ind[b] < ind[c])
partition_b.push_back(poss);
else if (ind[c] < ind[a] && ind[c] < ind[b])
partition_c.push_back(poss);
else
assert(false);
}

if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
{
if (solve(depth - 1, partition_a, false).size() && solve(depth - 1, partition_b, false).size() && solve(depth - 1, partition_c, false).size())
{
if (confirmed)
{
int result = getLightest(a, b, c);
if (result == a)
return solve(depth - 1, partition_a, true);
if (result == b)
return solve(depth - 1, partition_b, true);
if (result == c)
return solve(depth - 1, partition_c, true);
}
else
{
return {0};
}

assert(false);
}
}
}

{
vector<vector<int>> partition_a;
vector<vector<int>> partition_b;
vector<vector<int>> partition_c;

for (auto poss : possibilities)
{
vector<int> ind(7);
for (int i = 0; i < 6; i++)
ind[poss[i]] = i;

if ((ind[a] > ind[b] && ind[a] < ind[c]) || (ind[a] < ind[b] && ind[a] > ind[c]))
{
partition_a.push_back(poss);
}
else if ((ind[b] > ind[c] && ind[b] < ind[a]) || (ind[b] < ind[c] && ind[b] > ind[a]))
{
partition_b.push_back(poss);
}
else if ((ind[c] > ind[a] && ind[c] < ind[b]) || (ind[c] < ind[a] && ind[c] > ind[b]))
{
partition_c.push_back(poss);
}
else
{
assert(false);
}
}

if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
{
if (solve(depth - 1, partition_a, false).size() && solve(depth - 1, partition_b, false).size() && solve(depth - 1, partition_c, false).size())
{
if (confirmed)
{
int result = getMedian(a, b, c);
if (result == a)
return solve(depth - 1, partition_a, true);
if (result == b)
return solve(depth - 1, partition_b, true);
if (result == c)
return solve(depth - 1, partition_c, true);
}
else
{
return {0};
}

assert(false);
}
}
}

{
vector<vector<int>> partition_a;
vector<vector<int>> partition_b;
vector<vector<int>> partition_c;

for (auto poss : possibilities)
{
vector<int> ind(7);
for (int i = 0; i < 6; i++)
ind[poss[i]] = i;

if (ind[a] > ind[b] && ind[a] > ind[c])
{
partition_a.push_back(poss);
}
else if (ind[b] > ind[a] && ind[b] > ind[c])
{
partition_b.push_back(poss);
}
else if (ind[c] > ind[a] && ind[c] > ind[b])
{
partition_c.push_back(poss);
}
else
{
assert(false);
}
}

if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
{
if (solve(depth - 1, partition_a, false).size() && solve(depth - 1, partition_b, false).size() && solve(depth - 1, partition_c, false).size())
{
if (confirmed)
{
int result = getHeaviest(a, b, c);
if (result == a)
return solve(depth - 1, partition_a, true);
if (result == b)
return solve(depth - 1, partition_b, true);
if (result == c)
return solve(depth - 1, partition_c, true);
}
else
{
return {0};
}

assert(false);
}
}
}

for (int d = 1; d <= 6; d++)
{
if (d == a || d == b || d == c)
continue;

{
vector<vector<int>> partition_a;
vector<vector<int>> partition_b;
vector<vector<int>> partition_c;

for (auto poss : possibilities)
{
vector<int> ind(7);
for (int i = 0; i < 6; i++)
ind[poss[i]] = i;

int result = getNLghtest(ind, a, b, c, d);

if (result == a)
partition_a.push_back(poss);
else if (result == b)
partition_b.push_back(poss);
else if (result == c)
partition_c.push_back(poss);
else
assert(false);
}

if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
{
if (solve(depth - 1, partition_a, false).size() && solve(depth - 1, partition_b, false).size() && solve(depth - 1, partition_c, false).size())
{
if (confirmed)
{
int result = getNextLightest(a, b, c, d);
if (result == a)
return solve(depth - 1, partition_a, true);
if (result == b)
return solve(depth - 1, partition_b, true);
if (result == c)
return solve(depth - 1, partition_c, true);
}
else
{
return {0};
}

assert(false);
}
}
}
}
}
return {};
}

void orderCoins()
{
vector<vector<int>> possibilities;
vector<int> a = {1, 2, 3, 4, 5, 6};
do
{
possibilities.push_back(a);
} while (next_permutation(a.begin(), a.end()));

auto result = solve(6, possibilities, true);
answer(&result[0]);
}

#ifdef _DEBUG

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define MAXN 6
#define MAX_ANSWER_CALLS 1

static int realC[MAXN];
static int ind[MAXN];
static int numQueries;
static int numAnswerCalls;

static int arr[300];
static int arraySize;
static int ptr;

static void readAll()
{
ptr = 0;
arraySize = 0;
int x;
cin >> x;
arr[arraySize++] = x;

for (int i = 0; i < arr[0] * 6; i++)
{
cin >> x;
arr[arraySize++] = x;
assert(arraySize <= 300);
}
}

static int readInt()
{
assert(ptr < arraySize);
int res = arr[ptr++];
return res;
}

static void initNewTest()
{
for (int i = 0; i < MAXN; i++)
{
realC[i] = readInt();
realC[i]--;
ind[realC[i]] = i;
}

numQueries = 0;
numAnswerCalls = 0;
}

void answer(int C[])
{
int i;

numAnswerCalls++;
if (numAnswerCalls > MAX_ANSWER_CALLS)
return;

for (i = 0; i < 6; i++)
printf("%d ", C[i]);
printf("%d\n", numQueries);
}

static void checkQuery(int A, int B, int C, int D)
{
if (D == -1)
{
if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6)
assert(0);
if (A == B || B == C || A == C)
assert(0);
}
else
{
if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6 || D < 1 || D > 6)
assert(0);
if (A == B || A == C || A == D || B == C || B == D || C == D)
assert(0);
}
}

int getMedian(int A, int B, int C)
{
numQueries++;
checkQuery(A, B, C, -1);

A--;
B--;
C--;

if (ind[B] < ind[A] && ind[A] < ind[C])
return A + 1;

if (ind[C] < ind[A] && ind[A] < ind[B])
return A + 1;

if (ind[A] < ind[B] && ind[B] < ind[C])
return B + 1;

if (ind[C] < ind[B] && ind[B] < ind[A])
return B + 1;

return C + 1;
}

int getHeaviest(int A, int B, int C)
{
numQueries++;
checkQuery(A, B, C, -1);

A--;
B--;
C--;

if (ind[A] > ind[B] && ind[A] > ind[C])
return A + 1;

if (ind[B] > ind[A] && ind[B] > ind[C])
return B + 1;

return C + 1;
}

int getLightest(int A, int B, int C)
{
numQueries++;
checkQuery(A, B, C, -1);

A--;
B--;
C--;

if (ind[A] < ind[B] && ind[A] < ind[C])
return A + 1;

if (ind[B] < ind[A] && ind[B] < ind[C])
return B + 1;

return C + 1;
}

int getNextLightest(int A, int B, int C, int D)
{
int allLess = 1;

numQueries++;
checkQuery(A, B, C, D);

A--;
B--;
C--;
D--;

if (ind[A] > ind[D] || ind[B] > ind[D] || ind[C] > ind[D])
allLess = 0;

if (allLess == 1)
{
if (ind[A] < ind[B] && ind[A] < ind[C])
return A + 1;

if (ind[B] < ind[A] && ind[B] < ind[C])
return B + 1;

return C + 1;
}

if (ind[A] > ind[D])
{
if ((ind[A] < ind[B] || ind[B] < ind[D]) &&
(ind[A] < ind[C] || ind[C] < ind[D]))
return A + 1;
}

if (ind[B] > ind[D])
{
if ((ind[B] < ind[A] || ind[A] < ind[D]) &&
(ind[B] < ind[C] || ind[C] < ind[D]))
return B + 1;
}

return C + 1;
}

int main()
{

readAll();
fclose(stdin);

int T, i;

T = readInt();

init(T);

for (i = 1; i <= T; i++)
{
initNewTest();
orderCoins();
}

return 0;
}

#endif

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:30:15: warning: unused parameter 'T' [-Wunused-parameter]
   30 | void init(int T) {}
      |           ~~~~^
scales.cpp: In function 'std::vector<int> solve(int, std::vector<std::vector<int> >, bool)':
scales.cpp:115:71: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
  115 | if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:121:5: warning: declaration of 'result' shadows a global declaration [-Wshadow]
  121 | int result = getLightest(a, b, c);
      |     ^~~~~~
scales.cpp:67:13: note: shadowed declaration is here
   67 | vector<int> result;
      |             ^~~~~~
scales.cpp:168:71: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
  168 | if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:174:5: warning: declaration of 'result' shadows a global declaration [-Wshadow]
  174 | int result = getMedian(a, b, c);
      |     ^~~~~~
scales.cpp:67:13: note: shadowed declaration is here
   67 | vector<int> result;
      |             ^~~~~~
scales.cpp:221:71: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
  221 | if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:227:5: warning: declaration of 'result' shadows a global declaration [-Wshadow]
  227 | int result = getHeaviest(a, b, c);
      |     ^~~~~~
scales.cpp:67:13: note: shadowed declaration is here
   67 | vector<int> result;
      |             ^~~~~~
scales.cpp:261:5: warning: declaration of 'result' shadows a global declaration [-Wshadow]
  261 | int result = getNLghtest(ind, a, b, c, d);
      |     ^~~~~~
scales.cpp:67:13: note: shadowed declaration is here
   67 | vector<int> result;
      |             ^~~~~~
scales.cpp:273:71: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
  273 | if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:279:5: warning: declaration of 'result' shadows a global declaration [-Wshadow]
  279 | int result = getNextLightest(a, b, c, d);
      |     ^~~~~~
scales.cpp:67:13: note: shadowed declaration is here
   67 | vector<int> result;
      |             ^~~~~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:310:6: warning: declaration of 'result' shadows a global declaration [-Wshadow]
  310 | auto result = solve(6, possibilities, true);
      |      ^~~~~~
scales.cpp:67:13: note: shadowed declaration is here
   67 | vector<int> result;
      |             ^~~~~~

Subtask 10 / 100

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