| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 621320 | M_W | Scales (IOI15_scales) | C++17 | 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>
using namespace std;
vector<vector<int>> all_perm;
void init(int T){
vector<int> perm = {1, 2, 3, 4, 5, 6};
do{
all_perm.push_back(perm);
} while(next_permutation(perm.begin(), perm.end()));
}
void orderCoins(){
vector<vector<int>> cases = all_perm;
while(cases.size() > 1){
array<int, 7> ask = {INT_MAX, INT_MAX, 0, 0, 0, 0, 0};
for(int i = 1; i <= 6; i++){
for(int j = 1; j < i; j++){
for(int k = 1; k < j; k++){
int hi = 0, hj = 0, hk = 0; // heavy count
int li = 0, lj = 0, lk = 0; // light count
int mi = 0, mj = 0, mk = 0; // median count
for(auto x : cases){
int ii, jj, kk;
for(int p = 0; p < 6; p++){
if(x[p] == i) ii = p;
if(x[p] == j) jj = p;
if(x[p] == k) kk = p;
}
// Case1: Getheaviest
if(max({ii, jj, kk}) == ii) hi++;
if(max({ii, jj, kk}) == jj) hj++;
if(max({ii, jj, kk}) == kk) hk++;
// Case2: Getlightest
if(min({ii, jj, kk}) == ii) li++;
if(min({ii, jj, kk}) == jj) lj++;
if(min({ii, jj, kk}) == kk) lk++;
// Case3: GetMedian
if(min({ii, jj, kk}) != ii && max({ii, jj, kk}) != ii) mi++;
if(min({ii, jj, kk}) != jj && max({ii, jj, kk}) != jj) mj++;
if(min({ii, jj, kk}) != kk && max({ii, jj, kk}) != kk) mk++;
}
if(max({hi, hj, hk}) < ask[0] || (max({hi, hj, hk}) == ask[0] && hi + hj + hk < ask[6]))
ask = {max({hi, hj, hk}), 1, i, j, k, 0, hi + hj + hk};
if(max({li, lj, lk}) < ask[0] || (max({li, lj, lk}) == ask[0] && li + lj + lk < ask[6]))
ask = {max({li, lj, lk}), 2, i, j, k, 0, li + lj + lk};
if(max({mi, mj, mk}) < ask[0] || (max({mi, mj, mk}) == ask[0] && mi + mj + mk < ask[6]))
ask = {max({mi, mj, mk}), 3, i, j, k, 0, mi + mj + mk};
// Case4: GetNextLightest
for(int l = 1; l < k; l++){
int si = 0, sj = 0, sk = 0;
for(auto x : cases){
int l2, upb = 10;
int ii, jj, kk;
for(int p = 0; p < 6; p++){
if(x[p] == i) ii = p;
if(x[p] == j) jj = p;
if(x[p] == k) kk = p;
if(x[p] == l) l2 = p;
}
vector<int> tmp = {ii, jj, kk};
for(auto y : tmp){
if(y > l2) upb = min(upb, y);
}
if(upb == 10) upb = min({ii, jj, kk});
if(ii == upb) si++;
if(jj == upb) sj++;
if(kk == upb) sk++;
}
if(max({si, sj, sk}) < ask[0] || (max({si, sj, sk}) == ask[0] && si + sj + sk < ask[6]))
ask = {max({si, sj, sk}), 4, i, j, k, l, si + sj + sk};
}
}
}
}
int res;
vector<vector<int>> tmp = cases; cases.clear();
if(ask[1] == 1){
res = getHeaviest(ask[2], ask[3], ask[4]);
for(auto x : tmp){
int ii, jj, kk, rr;
for(int p = 0; p < 6; p++){
if(x[p] == ask[4]) ii = p;
if(x[p] == ask[2]) jj = p;
if(x[p] == ask[3]) kk = p;
if(x[p] == res) rr = p;
}
if(max({ii, jj, kk}) == rr) cases.push_back(x);
}
}
else if(ask[1] == 2){
res = getLightest(ask[4], ask[2], ask[3]);
for(auto x : tmp){
int ii, jj, kk, rr;
for(int p = 0; p < 6; p++){
if(x[p] == ask[4]) ii = p;
if(x[p] == ask[2]) jj = p;
if(x[p] == ask[3]) kk = p;
if(x[p] == res) rr = p;
}
if(min({ii, jj, kk}) == rr) cases.push_back(x);
}
}
else if(ask[1] == 3){
res = getMedian(ask[4], ask[2], ask[3]);
for(auto x : tmp){
int ii, jj, kk, rr;
for(int p = 0; p < 6; p++){
if(x[p] == ask[4]) ii = p;
if(x[p] == ask[2]) jj = p;
if(x[p] == ask[3]) kk = p;
if(x[p] == res) rr = p;
}
if(min({ii, jj, kk}) != rr && max({ii, jj, kk}) != rr) cases.push_back(x);
}
}
else{
res = getNextLightest(ask[2], ask[3], ask[4], ask[5]);
for(auto x : tmp){
int l2, upb = 10;
int ii, jj, kk, rr;
for(int p = 0; p < 6; p++){
if(x[p] == ask[2]) ii = p;
if(x[p] == ask[3]) jj = p;
if(x[p] == ask[4]) kk = p;
if(x[p] == ask[5]) l2 = p;
if(x[p] == res) rr = p;
}
vector<int> tmp = {ii, jj, kk};
for(auto y : tmp){
if(y > l2) upb = min(upb, y);
}
if(upb == 10) upb = min({ii, jj, kk});
if(upb == rr) cases.push_back(x);
}
}
}
int ans[] = {cases[0][0], cases[0][1], cases[0][2], cases[0][3], cases[0][4], cases[0][5]};
answer(ans);
}