| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 601571 | AmirElarbi | 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>
#define vi vector<int>
#define gi greater<int>
#define gr greater
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e9
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 2e5+5
using namespace std;
const int MOD = 1e9+7;
const int nax = 2e5+5;
typedef complex<int> Point;
#define X real()
#define Y imag()
//#include "scales.h"
using namespace std;
#define _MAXN 6
#define _MAX_ANSWER_CALLS 1
static int _realC[_MAXN];
static int _ind[_MAXN];
static int _numQueries;
static int _numAnswerCalls;
static FILE * _f;
static FILE * _of;
static int _getNumberOfTests() {
int T, ret;
_f = fopen("input.txt", "r");
_of = fopen("output.txt", "w");
ret = fscanf(_f, "%d", &T);
assert(ret == 1);
return T;
}
static void _initNewTest() {
int i, ret;
for (i = 0; i < _MAXN; i++) {
ret = fscanf(_f, "%d", &_realC[i]);
assert(ret == 1);
_realC[i]--;
_ind[_realC[i]] = i;
}
_numQueries = 0;
_numAnswerCalls = 0;
}
void answer(int W[]) {
int i;
_numAnswerCalls++;
if (_numAnswerCalls > _MAX_ANSWER_CALLS)
return;
for (i = 0; i < 6; i++)
fprintf(_of, "%d ", W[i]);
fprintf(_of, "\n%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;
}
void init(int T) {
}
void orderCoins() {
int ans[6] = {1, 2, 3, 4, 5, 6};
int hv1 = getHeaviest(1,2,3), hv2 = getHeaviest(4,5,6),
med1 = getMedian(1,2,3), med2 = getMedian(4,5,6),
lght1 = 0, lght2 = 0;
for (int i = 1; i <= 3; ++i)
{
if(i != hv1 && i != med1) lght1 = i;
}
for (int i = 4; i <= 6; ++i)
{
if(i != hv2 && i != med2) lght2 = i;
}
int lb1 = getNextLightest(hv1, med1, lght1, lght2);
if(lb1 == lght1){
int lb2 = getNextLightest(lght2, hv1, lght1, med2);
if(lb2 == lght2) {
ans[5] = hv2, ans[4] = med2;
int lb3 = getHeaviest(hv1, med1, lght2);
if(lb3 == lght1) ans[3] = lght2, ans[2] = hv1, ans[1] = med1, ans[0] = lght1;
else ans[3] = hv1, ans[2] = med1, ans[1] = lght1, ans[0] = lght2;
} else if(lb2 == lght1) {
int lb3 = getNextLightest(hv1, med1, lght1, hv2);
if(lb3 == med1) ans[0] = lght2, ans[1] = med2, ans[2] = lght1, ans[3] = hv2, ans[4] = med1, ans[5] = hv1;
else if(lb3 == hv1) ans[0] = lght2, ans[1] = med2, ans[2] = lght1, ans[3] = med1, ans[4] = hv2, ans[5] = hv1;
else {
int lb4 = getMedian(hv1,hv2,lght2);
if(lb4 == hv2) ans[0] = lght2, ans[1] = med2,ans[2] = hv2, ans[3] = lght1, ans[4] = med1, ans[5] = hv1;
else if(lb4 == hv1) ans[0] = lght2, ans[1] = med2, ans[2] = lght1, ans[3] = med1, ans[4] = hv1, ans[5] = hv2;
else ans[0] = lght1, ans[1] = med1, ans[2] = hv1, ans[3] = lght2, ans[4] = med2, ans[5] = hv2;
}
} else {
ans[0] = lght2, ans[1] = lght1, ans[2] = med1, ans[3] = med2;
int lb3 = getHeaviest(hv1,hv2,med2);
if(lb3 == hv1) ans[4] = hv2, ans[5] = hv1;
else ans[4] = hv1, ans[5] = hv2;
}
} else {
ans[0] = lght1;
if(lb1 == hv1) {
int lb2 = getNextLightest(hv2, med2, lght2, hv1);
ans[1] = med1;
ans[2] = lght2;
if(lb2 == lght2) ans[3] = med2, ans[4] = hv2, ans[5] = hv1;
else if(lb2 == med2) ans[3] = hv1, ans[4] = med2, ans[5] = hv2;
else ans[3] = med2, ans[4] = hv1, ans[5] = hv2;
}
else{
ans[1] = lght2;
int lb2 = getNextLightest(hv2, med2, med1, hv1), lb3 = getNextLightest(hv2, med2, hv1, med1);
if(lb2 == hv2){
ans[5] = hv2, ans[4] = hv1;
if(lb3 == med2) ans[3] = med2, ans[2] = med1;
else ans[3] = med1, ans[2] = med2;
} else if(lb2 == med2){
ans[5] = hv2, ans[4] = med2, ans[3] = hv1, ans[2] = med1;
} else {
ans[5] = hv1;
if(lb3 == hv2) ans[4] = hv2, ans[3] = med1, ans[2] = med2;
else if(lb3 == hv1) ans[4] = med1, ans[3] = hv2, ans[2] = med2;
else ans[4] = hv2, ans[3] = med2, ans[2] = med1;
}
}
}
answer(ans);
}
int main() {
int T, i;
T = _getNumberOfTests();
init(T);
for (i = 1; i <= T; i++) {
_initNewTest();
orderCoins();
}
return 0;
}