| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 588120 | MohamedFaresNebili | 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>
#include "scales.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
#define int ll
const int MOD = 1000 * 1000 * 1000 + 7;
void answer(int W[6]);
int getHeaviest(int A, int B, int C);
int getLightest(int A, int B, int C);
int getMedian(int A, int B, int C);
int getNextLightest(int A, int B, int C, int D);
struct node{
int A, B, C, D, T;
node() {};
node(int A, int B, int C, int D, int T):
A(A), B(B), C(C), D(D), T(T) {}
};
vector<vector<int>> V;
vector<node> Q;
void init(int T) {
vector<int> A(6);
for(int l = 0; l < 6; l++) A[l] = l;
do {
V.push_back(A);
} while(next_permutation(A.begin(), A.end()));
for(int l = 0; l < 6; l++)
for(int i = l + 1; i < 6; i++)
for(int j = i + 1; j < 6; j++)
Q.push_back({l, i, j, 0, 0}),
Q.push_back({l, i, j, 0, 1}),
Q.push_back({l, i, j, 0, 2});
for(int k = 0; k < 6; k++)
for(int l = 0; l < 6; l++)
for(int i = l + 1; i < 6; i++)
for(int j = i + 1; j < 6; j++) {
if(k == l || k == i || k == j) continue;
Q.push_back({l, i, j, k, 3});
}
return;
}
int med(int A, int B, int C) {
if(max({A, B, C}) != A && min({A, B, C}) != A) return A;
if(max({A, B, C}) != B && min({A, B, C}) != B) return B;
if(max({A, B, C}) != C && min({A, B, C}) != C) return C;
}
int nextL(int A, int B, int C, int D) {
int res = 1e9 + 7;
if(A > D) res = min(res, A);
if(B > D) res = min(res, B);
if(A > C) res = min(res, C);
if(res == 1e9 + 7) res = min({A, B, C});
return res;
}
void orderCoins(void) {
vector<vector<int>> perm = V;
while(perm.size() > 1) {
node query; int best = 1e9 + 7;
for(auto u : Q) {
if(u.T == 0) {
int A = 0, B = 0, C = 0;
for(auto v : perm) {
if(max({v[u.A], v[u.B], v[u.C]}) == v[u.A]) A++;
if(max({v[u.A], v[u.B], v[u.C]}) == v[u.B]) B++;
if(max({v[u.A], v[u.B], v[u.C]}) == v[u.C]) C++;
}
A = max({A, B, C});
if(best >= A)
best = A, query = u;
}
if(u.T == 1) {
int A = 0, B = 0, C = 0;
for(auto v : perm) {
if(min({v[u.A], v[u.B], v[u.C]}) == v[u.A]) A++;
if(min({v[u.A], v[u.B], v[u.C]}) == v[u.B]) B++;
if(min({v[u.A], v[u.B], v[u.C]}) == v[u.C]) C++;
}
A = max({A, B, C});
if(best >= A)
best = A, query = u;
}
if(u.T == 2) {
int A = 0, B = 0, C = 0;
for(auto v : perm) {
if(med(v[u.A], v[u.B], v[u.C]) == v[u.A]) A++;
if(med(v[u.A], v[u.B], v[u.C]) == v[u.B]) B++;
if(med(v[u.A], v[u.B], v[u.C]) == v[u.C]) C++;
}
A = max({A, B, C});
if(best >= A)
best = A, query = u;
}
if(u.T == 3) {
int A = 0, B = 0, C = 0;
for(auto v : perm) {
if(nextL(v[u.A], v[u.B], v[u.C], v[u.D]) == v[u.A]) A++;
if(nextL(v[u.A], v[u.B], v[u.C], v[u.D]) == v[u.B]) B++;
if(nextL(v[u.A], v[u.B], v[u.C], v[u.D]) == v[u.C]) C++;
}
A = max({A, B, C});
if(best >= A)
best = A, query = u;
}
}
vector<vector<int>> P;
if(query.T == 0) {
int K = getHeaviest(query.A + 1, query.B + 1, query.C + 1);
for(auto u : perm) {
if(max({u[query.A], u[query.B], u[query.C]}) == u[K]) P.pb(u);
}
}
if(query.T == 1) {
int K = getLightest(query.A + 1, query.B + 1, query.C + 1);
for(auto u : perm) {
if(min({u[query.A], u[query.B], u[query.C]}) == u[K]) P.pb(u);
}
}
if(query.T == 2) {
int K = getMedian(query.A + 1, query.B + 1, query.C + 1);
for(auto u : perm) {
if(med(u[query.A], u[query.B], u[query.C]) == u[K]) P.pb(u);
}
}
if(query.T == 3) {
int K = getNextLightest(query.A + 1, query.B + 1, query.C + 1, query.D + 1);
for(auto u : perm) {
if(nextL(u[query.A], u[query.B], u[query.C], u[query.D]) == u[K]) P.pb(u);
}
}
swap(P, perm);
}
int res[6];
for(int l = 0; l < 6; l++)
res[perm[0][l]] = l + 1;
answer(res);
}