Submission #981267

#	Time	Username	Problem	Language	Result	Execution time	Memory
981267		GrindMachine	Scales (IOI15_scales)	C++17	100 / 100	119 ms	1128 KiB

scales

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "scales.h"

int n = 6;
vector<int> pow3(15);
vector<array<int,5>> ops;
map< pair<vector<array<int,6>>,int>, pii> mp;

bool go(vector<array<int,6>> &a, int m){
    // can make m more guesses
    if(m < 0) return false;
    if(sz(a) > pow3[m]) return false;
    if(sz(a) <= 1) return true;
    if(m == 0) return false;

    rep(ind,sz(ops)){
        auto [i,j,k,l,t] = ops[ind];
        vector<array<int,6>> nxt[3];

        trav(v,a){       
            array<pii,3> ar = { make_pair(v[i],0), make_pair(v[j],1), make_pair(v[k],2) };
            sort(all(ar)); 
            if(t <= 2){
                nxt[ar[t].ss].pb(v);
            }
            else{
                bool ok = false;
                rep(j,3){
                    if(ar[j].ff > v[l]){
                        nxt[ar[j].ss].pb(v);
                        ok = true;
                        break;
                    }
                }

                if(!ok){
                    nxt[ar[0].ss].pb(v);
                }
            }
        }

        array<pii,3> ar = { make_pair(sz(nxt[0]),0), make_pair(sz(nxt[1]),1), make_pair(sz(nxt[2]),2) };
        sort(rall(ar));

        bool ans = true;
        rep(j,3){
            ans &= go(nxt[ar[j].ss],m-1);
            if(!ans) break;
        }

        mp[{a,m}] = {ind,1};
        if(ans) return true;
    }

    mp[{a,m}] = {-1,0};
    return false;
}

vector<vector<array<int,6>>> here;
vector<vector<int>> adj;
vector<int> op;

void init(int T){
    pow3[0] = 1;
    rep1(i,10) pow3[i] = pow3[i-1]*3;

    rep(i,n){
        for(int j = i+1; j < n; ++j){
            for(int k = j+1; k < n; ++k){
                rep(t,3){
                    ops.pb({i,j,k,-1,t});
                }

                rep(l,n){
                    if(l == i or l == j or l == k) conts;
                    ops.pb({i,j,k,l,3});
                }
            }
        }
    }

    vector<array<int,6>> perms;
    array<int,6> a;
    iota(all(a),1);

    do{

        perms.pb(a);

    } while(next_permutation(all(a)));

    int ptr = 0;

    auto new_node = [&](vector<array<int,6>> v){
        adj.pb(vector<int>());
        here.pb(v);
        op.pb(0);
        return ptr++;
    };

    queue<tuple< vector<array<int,6>>, int, int>> q;
    q.push({perms,6,new_node(perms)});

    while(!q.empty()){
        auto [a,m,u] = q.front();
        q.pop();
        if(sz(a) <= 1) conts;
        assert(m >= 1);

        assert(go(a,m));
        auto [ind,ok] = mp[{a,m}];
        assert(ok);

        op[u] = ind;
        auto [i,j,k,l,t] = ops[ind];

        vector<array<int,6>> nxt[3];

        trav(v,a){       
            array<pii,3> ar = { make_pair(v[i],0), make_pair(v[j],1), make_pair(v[k],2) };
            sort(all(ar)); 
            if(t <= 2){
                nxt[ar[t].ss].pb(v);
            }
            else{
                bool ok = false;
                rep(j,3){
                    if(ar[j].ff > v[l]){
                        nxt[ar[j].ss].pb(v);
                        ok = true;
                        break;
                    }
                }

                if(!ok){
                    nxt[ar[0].ss].pb(v);
                }
            }
        }

        rep(j,3){
            int v = new_node(nxt[j]);
            adj[u].pb(v);
            q.push({nxt[j],m-1,v});
        }
    }
}

void found(array<int,6> a){
    int ans[6];
    rep(i,6) ans[a[i]-1] = i+1;
    answer(ans);
}

void orderCoins() {
    int u = 0;
    while(true){
        auto &a = here[u];
        if(sz(a) == 1){
            found(a[0]);
            return;
        }

        int ind = op[u];
        auto [i,j,k,l,t] = ops[ind];
        i++, j++, k++, l++;
        ll res = 0;

        if(t == 0){
            res = getLightest(i,j,k);
        }
        else if(t == 1){
            res = getMedian(i,j,k);
        }
        else if(t == 2){
            res = getHeaviest(i,j,k);
        }
        else{
            res = getNextLightest(i,j,k,l);
        }

        if(res == i){
            u = adj[u][0];
        }
        else if(res == j){
            u = adj[u][1];
        }
        else{
            u = adj[u][2];
        }
    }
}

Compilation message (stderr)

scales.cpp: In function 'bool go(std::vector<std::array<int, 6> >&, int)':
scales.cpp:87:21: warning: declaration of 'j' shadows a previous local [-Wshadow]
   87 |                 rep(j,3){
      |                     ^
scales.cpp:28:26: note: in definition of macro 'rep'
   28 | #define rep(i,n) for(int i = 0; i < n; ++i)
      |                          ^
scales.cpp:76:17: note: shadowed declaration is here
   76 |         auto [i,j,k,l,t] = ops[ind];
      |                 ^
scales.cpp:105:13: warning: declaration of 'j' shadows a previous local [-Wshadow]
  105 |         rep(j,3){
      |             ^
scales.cpp:28:26: note: in definition of macro 'rep'
   28 | #define rep(i,n) for(int i = 0; i < n; ++i)
      |                          ^
scales.cpp:76:17: note: shadowed declaration is here
   76 |         auto [i,j,k,l,t] = ops[ind];
      |                 ^
scales.cpp: In function 'void init(int)':
scales.cpp:164:15: warning: declaration of 'a' shadows a previous local [-Wshadow]
  164 |         auto [a,m,u] = q.front();
      |               ^
scales.cpp:142:18: note: shadowed declaration is here
  142 |     array<int,6> a;
      |                  ^
scales.cpp:185:22: warning: declaration of 'ok' shadows a previous local [-Wshadow]
  185 |                 bool ok = false;
      |                      ^~
scales.cpp:170:19: note: shadowed declaration is here
  170 |         auto [ind,ok] = mp[{a,m}];
      |                   ^~
scales.cpp:186:21: warning: declaration of 'j' shadows a previous local [-Wshadow]
  186 |                 rep(j,3){
      |                     ^
scales.cpp:28:26: note: in definition of macro 'rep'
   28 | #define rep(i,n) for(int i = 0; i < n; ++i)
      |                          ^
scales.cpp:174:17: note: shadowed declaration is here
  174 |         auto [i,j,k,l,t] = ops[ind];
      |                 ^
scales.cpp:200:13: warning: declaration of 'j' shadows a previous local [-Wshadow]
  200 |         rep(j,3){
      |             ^
scales.cpp:28:26: note: in definition of macro 'rep'
   28 | #define rep(i,n) for(int i = 0; i < n; ++i)
      |                          ^
scales.cpp:174:17: note: shadowed declaration is here
  174 |         auto [i,j,k,l,t] = ops[ind];
      |                 ^
scales.cpp:122:15: warning: unused parameter 'T' [-Wunused-parameter]
  122 | void init(int T){
      |           ~~~~^

• Subtask 1: 100 / 100