| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1121131 | SalihSahin | 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 pb push_back
using namespace std;
//#include "scales.h"
#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;
ret = scanf("%d", &T);
assert(ret == 1);
return T;
}
static void _initNewTest() {
int i, ret;
for (i = 0; i < _MAXN; i++) {
ret = scanf("%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++)
printf("%d ", W[i]);
printf("\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;
}
vector<int> perm(6);
void init(int T) {
for(int i = 0; i < 6; i++) perm[i] = i+1;
}
void orderCoins(){
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
shuffle(perm.begin(), perm.end(), rng);
int W[6];
int x = getLightest(perm[0], perm[1], perm[2]);
vector<int> rem;
for(int i = 0; i < 3; i++){
if(perm[i] != x) rem.pb(perm[i]);
}
int y = getHeaviest(rem[0], rem[1], perm[3]);
vector<int> rem2;
for(int i = 0; i < 4; i++){
if(perm[i] != y && perm[i] != x) rem2.pb(perm[i]);
}
int z = getMedian(rem2[0], rem2[1], x);
vector<int> l = {-1, -1, -1, y};
if(z == x){
l[1] = x;
l[2] = rem2[0];
l[0] = rem2[1];
}
else if(z == rem2[0]){
l[0] = x;
l[1] = z;
l[2] = rem2[1];
}
else{
l[0] = x;
l[1] = rem2[1];
l[2] = rem2[0];
}
//for(int i = 0; i < 4; i++) cout<<l[i]<<" ";
//cout<<endl;
// 1, 2, 3, 4 ---- 5 ve 6 kaldı 3 islemde
vector<int> l2 = {-1, -1, -1, -1, -1};
int k = getMedian(l[0], l[2], perm[4]);
if(k == perm[4]){
int k2 = getMedian(l[0], l[1], perm[4]);
if(k2 == l[1]) l2 = {l[0], l[1], perm[4], l[2], l[3]};
else l2 = {l[0], perm[4], l[1], l[2], l[3]};
}
else if(k == l[0]) l2 = {perm[4], l[0], l[1], l[2], l[3]};
else if(k == l[2]){
int k2 = getMedian(l[2], l[3], perm[4]);
if(k2 == l[3]) l2 = {l[0], l[1], l[2], l[3], perm[4]};
else l2 = {l[0], l[1], l[2], perm[4], l[3]};
}
l = l2;
//for(int i = 0; i < 5; i++) cout<<l[i]<<" ";
//cout<<endl;
vector<int> res = {-1, -1, -1, -1, -1, -1};
k = getMedian(l[1], l[3], perm[5]);
if(k == perm[5]){
int k2 = getMedian(l[1], l[2], perm[5]);
if(k2 == l[2]) res = {l[0], l[1], l[2], perm[5], l[3], l[4]};
else res = {l[0], l[1], perm[5], l[2], l[3], l[4]};
}
else if(k == l[1]){
int k2 = getMedian(l[0], l[1], perm[5]);
if(k2 == l[0]) res = {perm[5], l[0], l[1], l[2], l[3], l[4]};
else res = {l[0], perm[5], l[1], l[2], l[3], l[4]};
}
else if(k == l[3]){
int k2 = getMedian(l[3], l[4], perm[5]);
if(k2 == l[4]) res = {l[0], l[1], l[2], l[3], l[4], perm[5]};
else res = {l[0], l[1], l[2], l[3], perm[5], l[4]};
}
for(int i = 0; i < 6; i++){
W[i] = res[i];
}
answer(W);
}
int main() {
int T, i;
T = _getNumberOfTests();
init(T);
for (i = 1; i <= T; i++) {
_initNewTest();
orderCoins();
}
return 0;
}