| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1047592 | Alihan_8 | Scales (IOI15_scales) | C++17 | 30 ms | 896 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 "scales.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define ln '\n'
vector <vector<int>> P;
int GetMin(int a, int b, int c, int j){
auto &p = P[j];
if ( p[a] < min(p[b], p[c]) ) return 0;
return p[b] < p[c] ? 1 : 2;
}
int GetMax(int a, int b, int c, int j){
auto &p = P[j];
if ( p[a] > max(p[b], p[c]) ) return 0;
return p[b] > p[c] ? 1 : 2;
}
int GetMed(int a, int b, int c, int j){
int x = GetMax(a, b, c, j), y = GetMin(a, b, c, j);
for ( auto t: {0, 1, 2} ){
if ( t != x && t != y ){
return t;
}
}
return -1;
}
int GetNext(int k, int a, int b, int c, int j){
auto &p = P[j];
if ( min({p[a], p[b], p[c]}) > p[k] || max({p[a], p[b], p[c]}) < p[k] ){
return GetMin(a, b, c, j);
}
vector <int> aux = {a, b, c};
int x = aux[GetMed(a, b, c, j)];
if ( p[x] > p[k] ) return GetMed(a, b, c, j);
return GetMax(a, b, c, j);
}
struct qry{
int t;
vector <int> id;
qry(int t = -1, vector <int> id = {}) : t(t), id(id) {}
int eval(int j){
if ( t == 0 ) return GetMin(id[0], id[1], id[2], j);
if ( t == 1 ) return GetMax(id[0], id[1], id[2], j);
if ( t == 2 ) return GetMed(id[0], id[1], id[2], j);
return GetNext(id[0], id[1], id[2], id[3], j);
}
};
struct Info{
qry t;
vector <int> ch;
Info(qry t = qry(), vector <int> ch = {-1, -1, -1}) : t(t), ch(ch) {}
};
vector <qry> Q;
vector <Info> trie;
int ct, root;
map <vector<int>,int> mp;
map <int,vector<int>> rv;
int C[] = {243, 81, 27, 9, 3, 1};
int build(vector <int> id, int h){
if ( mp.count(id) ){
return mp[id];
}
int &ret = mp[id]; ret = -1;
if ( (int)id.size() <= 1 ){
ret = ct++;
if ( !id.empty() ){
rv[ret] = P[id[0]];
}
trie.pb(Info());
return ret;
}
assert(h < 6);
for ( int i = 0; i < (int)Q.size(); i++ ){
auto op = Q[i];
vector <vector<int>> nxt(3);
for ( auto &j: id ){
nxt[op.eval(j)].pb(j);
}
int mx = 0;
for ( auto j: {0, 1, 2} ){
mx = max((int)nxt[j].size(), mx);
}
if ( mx > C[h] ) continue;
vector <int> ch(3);
for ( auto j: {0, 1, 2} ){
ch[j] = build(nxt[j], h + 1);
}
if ( min({ch[0], ch[1], ch[2]}) == -1 ){
continue;
}
ret = ct++;
trie.pb(Info(op, ch));
break;
}
return ret;
}
void init(int T) {
for ( int i = 0; i < 6; i++ ){
for ( int j = i + 1; j < 6; j++ ){
for ( int k = j + 1; k < 6; k++ ){
for ( auto t: {0, 1, 2} ){
Q.pb(qry(t, {i, j, k}));
}
for ( int l = 0; l < 6; l++ ){
if ( l != i && l != j && l != k ){
Q.pb(qry(3, {l, i, j, k}));
}
}
}
}
}
vector <int> p(6);
iota(all(p), 0);
do{
P.pb(p);
} while ( next_permutation(all(p)) );
vector <int> id;
for ( int i = 0; i < 720; i++ ){
id.pb(i);
}
root = build(id, 0);
}
vector <int> get(int u){
if ( trie[u].ch[0] == -1 ){ // leaf
return rv[u];
}
int t = trie[u].t.t, x = -1;
auto &id = trie[u].t.id;
if ( t == 0 ) x = getLightest(id[0] + 1, id[1] + 1, id[2] + 1);
if ( t == 1 ) x = getHeaviest(id[0] + 1, id[1] + 1, id[2] + 1);
if ( t == 2 ) x = getMedian(id[0] + 1, id[1] + 1, id[2] + 1);
if ( t == 3 ) x = getNextLightest(id[1] + 1, id[2] + 1, id[3] + 1, id[0] + 1);
int nxt = -1;
for ( auto j: {0, 1, 2, 3} ){
if ( j < (int)id.size() && x == id[j] + 1 ){
nxt = j;
}
}
nxt -= (t == 3);
return get(trie[u].ch[nxt]);
}
void orderCoins() {
auto ans = get(root);
int w[6];
for ( int i = 0; i < 6; i++ ){
w[ans[i]] = i + 1;
}
answer(w);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||