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;
typedef long long ll;
vector<vector<int>> perms(720);
void init(int T) {
for (int i = 0; i < 720; i++) {
perms[i] = {1, 2, 3, 4, 5, 6};
swap(perms[i][0], perms[i][0 + ((i) % 6)]);
swap(perms[i][1], perms[i][1 + ((i/6) % 5)]);
swap(perms[i][2], perms[i][2 + ((i/6/5) % 4)]);
swap(perms[i][3], perms[i][3 + ((i/6/5/4) % 3)]);
swap(perms[i][4], perms[i][4 + ((i/6/5/4/3) % 2)]);
}
}
int maxPossAfterLow(vector<bool> &poss, int a, int b, int c) {
int mxA = 0, mxB = 0, mxC = 0;
for (int i = 0; i < 720; i++) {
if (!poss[i]) continue;
int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
if (idA < idB && idA < idC) mxA++;
if (idB < idA && idB < idC) mxB++;
if (idC < idB && idC < idA) mxC++;
}
return max({mxA, mxB, mxC});
}
int maxPossAfterMid(vector<bool> &poss, int a, int b, int c) {
int mxA = 0, mxB = 0, mxC = 0;
for (int i = 0; i < 720; i++) {
if (!poss[i]) continue;
int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
if ((idA < idB) != (idA < idC)) mxA++;
if ((idB < idA) != (idB < idC)) mxB++;
if ((idC < idB) != (idC < idA)) mxC++;
}
return max({mxA, mxB, mxC});
}
int maxPossAfterHigh(vector<bool> &poss, int a, int b, int c) {
int mxA = 0, mxB = 0, mxC = 0;
for (int i = 0; i < 720; i++) {
if (!poss[i]) continue;
int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
if (idA > idB && idA > idC) mxA++;
if (idB > idA && idB > idC) mxB++;
if (idC > idB && idC > idA) mxC++;
}
return max({mxA, mxB, mxC});
}
void queryLow(vector<bool> &poss, ll &possCnt, int a, int b, int c) {
int t = getLightest(a, b, c);
for (int i = 0; i < 720; i++) {
if (!poss[i]) continue;
int idT = find(perms[i].begin(), perms[i].end(), t) - perms[i].begin();
int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
if (idT > idA || idT > idB || idT > idC) { poss[i] = false; possCnt--; }
}
}
void queryMid(vector<bool> &poss, ll &possCnt, int a, int b, int c) {
int t = getMedian(a, b, c);
for (int i = 0; i < 720; i++) {
if (!poss[i]) continue;
int idT = find(perms[i].begin(), perms[i].end(), t) - perms[i].begin();
int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
if (idT <= idA && idT <= idB && idT <= idC) { poss[i] = false; possCnt--; }
if (idT >= idA && idT >= idB && idT >= idC) { poss[i] = false; possCnt--; }
}
}
void queryHigh(vector<bool> &poss, ll &possCnt, int a, int b, int c) {
int t = getHeaviest(a, b, c);
for (int i = 0; i < 720; i++) {
if (!poss[i]) continue;
int idT = find(perms[i].begin(), perms[i].end(), t) - perms[i].begin();
int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
if (idT < idA || idT < idB || idT < idC) { poss[i] = false; possCnt--; }
}
}
void query(vector<bool> &poss, ll &possCnt) {
int mnCnt = 720;
int mnSetting = 0;
int mnA = 1, mnB = 2, mnC = 3;
for (int a = 1; a <= 6; a++) {
for (int b = a+1; b <= 6; b++) {
for (int c = b+1; c <= 6; c++) {
int low = maxPossAfterLow(poss, a, b, c);
int mid = maxPossAfterMid(poss, a, b, c);
int high = maxPossAfterHigh(poss, a, b, c);
if (low < mnCnt) {
mnCnt = low;
mnSetting = 0;
mnA = a; mnB = b; mnC = c;
}
if (mid < mnCnt) {
mnCnt = mid;
mnSetting = 1;
mnA = a; mnB = b; mnC = c;
}
if (high < mnCnt) {
mnCnt = high;
mnSetting = 2;
mnA = a; mnB = b; mnC = c;
}
}
}
}
if (mnSetting == 0) queryLow(poss, possCnt, mnA, mnB, mnC);
if (mnSetting == 1) queryMid(poss, possCnt, mnA, mnB, mnC);
if (mnSetting == 2) queryHigh(poss, possCnt, mnA, mnB, mnC);
}
void orderCoins() {
vector<bool> poss(720, true);
ll possCnt = 720;
while (possCnt > 1) {
query(poss, possCnt);
}
for (int i = 0; i < 720; i++) {
if (!poss[i]) continue;
int* W = &(perms[i][0]);
answer(W);
}
}
Compilation message (stderr)
scales.cpp: In function 'void init(int)':
scales.cpp:9:15: warning: unused parameter 'T' [-Wunused-parameter]
9 | void init(int T) {
| ~~~~^
scales.cpp: In function 'int maxPossAfterLow(std::vector<bool>&, int, int, int)':
scales.cpp:24:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
24 | int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:25:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
25 | int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:26:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
26 | int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'int maxPossAfterMid(std::vector<bool>&, int, int, int)':
scales.cpp:38:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
38 | int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:39:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
39 | int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:40:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
40 | int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'int maxPossAfterHigh(std::vector<bool>&, int, int, int)':
scales.cpp:52:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
52 | int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:53:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
53 | int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:54:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
54 | int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void queryLow(std::vector<bool>&, ll&, int, int, int)':
scales.cpp:66:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
66 | int idT = find(perms[i].begin(), perms[i].end(), t) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:67:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
67 | int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:68:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
68 | int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:69:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
69 | int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void queryMid(std::vector<bool>&, ll&, int, int, int)':
scales.cpp:78:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
78 | int idT = find(perms[i].begin(), perms[i].end(), t) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:79:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
79 | int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:80:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
80 | int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:81:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
81 | int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void queryHigh(std::vector<bool>&, ll&, int, int, int)':
scales.cpp:91:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
91 | int idT = find(perms[i].begin(), perms[i].end(), t) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:92:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
92 | int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:93:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
93 | int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:94:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
94 | int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
