Submission #424013

#	Time	Username	Problem	Language	Result	Execution time	Memory
424013		MarcoMeijer	Scales (IOI15_scales)	C++14	72.62 / 100	167 ms	452 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cerr << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }

vector<vi> possible, three, four;

void init(int T) {
    vi v = {1,2,3,4,5,6};
    RE(_,720) {
        possible.pb(v);
        next_permutation(all(v));
    }

    RE1(i,6) {
        REP(j,i+1,7) {
            REP(k,j+1,7) {
                three.pb({i,j,k});
                REP(l,k+1,7) {
                    four.pb({j,k,l,i});
                    four.pb({i,k,l,j});
                    four.pb({i,j,l,k});
                    four.pb({i,j,k,l});
                }
            }
        }
    }

    random_shuffle(all(three),[](int i){return rng()%i;});
    random_shuffle(all(four),[](int i){return rng()%i;});
}


int getL(vi v, int a, int b, int c) {
    REP(i,0,6)
        if(v[i] == a || v[i] == b || v[i] == c)
            return v[i];
    return -1;
}
int getM(vi v, int a, int b, int c) {
    int i=0;
    for(; 1; i++)
        if(v[i] == a || v[i] == b || v[i] == c)
            break;
    i++;
    for(; 1; i++)
        if(v[i] == a || v[i] == b || v[i] == c)
            return v[i];
    return -1;
}
int getH(vi v, int a, int b, int c) {
    REV(i,0,6)
        if(v[i] == a || v[i] == b || v[i] == c)
            return v[i];
    return -1;
}
int getN(vi v, int a, int b, int c, int d) {
    int enc = 0;
    RE(i,6) {
        if(enc && (v[i] == a || v[i] == b || v[i] == c))
            return v[i];
        if(v[i] == d)
            enc = 1;
        if(i == 5)
            i = -1;
    }
    return -1;
}

void Answer(vi v) {
    int W[] = {0, 0, 0, 0, 0, 0};
    RE(i,6) W[i] = v[i];
    answer(W);
}
void orderCoins() {
    vi a;
    RE(i,720) a.pb(i);

    while(a.size() != 1) {
        int mn = a.size();
        RE(q,2) {
            bool stop = false;
            FOR(v,four) {
                // next
                {
                    map<int,int> cnt;
                    FOR(i,a) cnt[getN(possible[i],v[0],v[1],v[2],v[3])]++;
                    int cmx = 0;
                    FOR(p,cnt) cmx = max(cmx, p.se);
                    mn = min(mn, cmx);

                    if(q && mn == cmx) {
                        vi na;
                        int res = getNextLightest(v[0],v[1],v[2],v[3]);
                        FOR(i,a)
                            if(getN(possible[i],v[0],v[1],v[2],v[3]) == res)
                                na.pb(i);
                        a = na;
                        stop = true;
                        break;
                    }
                }
            }
            if(stop)
                break;
            FOR(v,three) {
                // lightest
                {
                    map<int,int> cnt;
                    FOR(i,a) cnt[getL(possible[i],v[0],v[1],v[2])]++;
                    int cmx = 0;
                    FOR(p,cnt) cmx = max(cmx, p.se);
                    mn = min(mn, cmx);

                    if(q && mn == cmx) {
                        vi na;
                        int res = getLightest(v[0],v[1],v[2]);
                        FOR(i,a)
                            if(getL(possible[i],v[0],v[1],v[2]) == res)
                                na.pb(i);
                        a = na;
                        break;
                    }
                }

                // median
                {
                    map<int,int> cnt;
                    FOR(i,a) cnt[getM(possible[i],v[0],v[1],v[2])]++;
                    int cmx = 0;
                    FOR(p,cnt) cmx = max(cmx, p.se);
                    mn = min(mn, cmx);

                    if(q && mn == cmx) {
                        vi na;
                        int res = getMedian(v[0],v[1],v[2]);
                        FOR(i,a)
                            if(getM(possible[i],v[0],v[1],v[2]) == res)
                                na.pb(i);
                        a = na;
                        break;
                    }
                }
                
                // heaviest
                {
                    map<int,int> cnt;
                    FOR(i,a) cnt[getH(possible[i],v[0],v[1],v[2])]++;
                    int cmx = 0;
                    FOR(p,cnt) cmx = max(cmx, p.se);
                    mn = min(mn, cmx);

                    if(q && mn == cmx) {
                        vi na;
                        int res = getHeaviest(v[0],v[1],v[2]);
                        FOR(i,a)
                            if(getH(possible[i],v[0],v[1],v[2]) == res)
                                na.pb(i);
                        a = na;
                        break;
                    }
                }
            }
        }
    }

    Answer(possible[a[0]]);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:45:15: warning: unused parameter 'T' [-Wunused-parameter]
   45 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:117:24: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  117 |         int mn = a.size();
      |                  ~~~~~~^~

• Subtask 1: 72.619048 / 100