| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 621407 | M_W | Scales (IOI15_scales) | C++17 | 118 ms | 440 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>
#include "scales.h"
using namespace std;
vector<vector<int>> all_perm;
int A = 37, B = 61, M = 9122, last = 1;
int randInt(){
last = ((last * A) + B) % M;
return last;
}
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()));
}
bool condition(int i1, int j1, int k1, int i2, int j2, int k2, int type1, int type2, int x1, int y1, int z1, int x2, int y2, int z2){
// Check to choose 1 instead of 2
int mx1 = max({i1, j1, k1}), mx2 = max({i2, j2, k2});
int mn1 = min({i1, j1, k1}), mn2 = min({i2, j2, k2});
int sm1 = i1 + j1 + k1, sm2 = i2 + j2 + k2;
int r = randInt();
return mx1 < mx2 || (mx1 == mx2 && type1 > type2) || (mx1 == mx2 && type1 == type2 && x1 >= x2);
}
void orderCoins(){
vector<vector<int>> cases = all_perm;
while(cases.size() > 1){
array<int, 9> ask = {INT_MAX, 0, 0, 0, 0, 0, 1000, 1000, 1000};
for(int i = 1; i <= 6; i++){
for(int j = i + 1; j <= 6; j++){
for(int k = j + 1; k <= 6; k++){
int hi = 0, hj = 0, hk = 0; // heavy count (case left)
int li = 0, lj = 0, lk = 0; // light count (case left)
int mi = 0, mj = 0, mk = 0; // median count (case left)
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(condition(hi, hj, hk, ask[6], ask[7], ask[8], 1, ask[1], i, j, k, ask[2], ask[3], ask[4]))
ask = {max({hi, hj, hk}), 1, i, j, k, 0, hi, hj, hk};
if(condition(li, lj, lk, ask[6], ask[7], ask[8], 2, ask[1], i, j, k, ask[2], ask[3], ask[4]))
ask = {max({li, lj, lk}), 2, i, j, k, 0, li, lj, lk};
if(condition(mi, mj, mk, ask[6], ask[7], ask[8], 3, ask[1], i, j, k, ask[2], ask[3], ask[4]))
ask = {max({mi, mj, mk}), 3, i, j, k, 0, mi, mj, mk};
// Case4: GetNextLightest
for(int l = 1; l < 6; l++){
if(l == i || l == j || l == k) continue;
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] == l) ii = p;
if(x[p] == j) jj = p;
if(x[p] == k) kk = p;
if(x[p] == i) 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(condition(si, sj, sk, ask[6], ask[7], ask[8], 4, ask[1], i, j, k, ask[2], ask[3], ask[4]))
ask = {max({si, sj, sk}), 4, l, j, k, i, 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);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||