Submission #980828

#	Time	Username	Problem	Language	Result	Execution time	Memory
980828		GrindMachine	Scales (IOI15_scales)	C++17	0 / 100	296 ms	79492 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"

ll n = 6;
vector<ll> pow3(15);
vector<array<ll,4>> ops;
map< tuple< vector<vector<ll>>, ll, ll>, bool > mp;

bool go(vector<vector<ll>> &a, ll ind, ll m){
    // can make m more guesses
    if(m < 0) return false;
    if(sz(a) > pow3[m]) return false;
    if(m == 0) return true;
    if(ind >= sz(ops)) return false;
    if(mp.count({a,ind,m})) return mp[{a,ind,m}];

    // do op
    auto [i,j,k,t] = ops[ind];
    vector<vector<ll>> v1,v2,v3;
    trav(v,a){
        if(t == 0){
            if(v[i] < v[j] and v[i] < v[k]){
                v1.pb(v);
            }
            else if(v[j] < v[i] and v[j] < v[k]){
                v2.pb(v);
            }
            else{
                v3.pb(v);
            }
        }
        else if(t == 1){
            if(v[i] > min(v[j],v[k]) and v[i] < max(v[j],v[k])){
                v1.pb(v);
            }
            else if(v[j] > min(v[i],v[k]) and v[j] < max(v[i],v[k])){
                v2.pb(v);
            }
            else{
                v3.pb(v);
            }
        }
        else if(t == 2){
            if(v[i] > v[j] and v[i] > v[k]){
                v1.pb(v);
            }
            else if(v[j] > v[i] and v[j] > v[k]){
                v2.pb(v);
            }
            else{
                v3.pb(v);
            }
        }
    }

    bool ans = go(v1,ind+1,m-1)&go(v2,ind+1,m-1)&go(v3,ind+1,m-1);
    if(ans) return true;

    // skip
    ans = go(a,ind+1,m);
    return mp[{a,ind,m}] = ans;
}

vector<vector<ll>> adj;
vector<vector<vector<ll>>> here;
vector<ll> 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,t});
                }
            }
        }
    }

    // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    mt19937 rng(1);
    shuffle(all(ops),rng);

    vector<vector<ll>> perms;
    vector<ll> a(n);
    iota(all(a),1);

    do{

        perms.pb(a);

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

    bool ok = go(perms,0,7);

    ll ptr = 0;

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

    queue<tuple< vector<vector<ll>>, ll, ll, ll>> q;
    q.push({perms,0,7,new_node(perms)});

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

        for(int opi = ind; opi < sz(ops); ++opi){
            auto [i,j,k,t] = ops[opi];
            vector<vector<ll>> v1,v2,v3;
            trav(v,a){
                if(t == 0){
                    if(v[i] < v[j] and v[i] < v[k]){
                        v1.pb(v);
                    }
                    else if(v[j] < v[i] and v[j] < v[k]){
                        v2.pb(v);
                    }
                    else{
                        v3.pb(v);
                    }
                }
                else if(t == 1){
                    if(v[i] > min(v[j],v[k]) and v[i] < max(v[j],v[k])){
                        v1.pb(v);
                    }
                    else if(v[j] > min(v[i],v[k]) and v[j] < max(v[i],v[k])){
                        v2.pb(v);
                    }
                    else{
                        v3.pb(v);
                    }
                }
                else if(t == 2){
                    if(v[i] > v[j] and v[i] > v[k]){
                        v1.pb(v);
                    }
                    else if(v[j] > v[i] and v[j] > v[k]){
                        v2.pb(v);
                    }
                    else{
                        v3.pb(v);
                    }
                }
            }

            bool res = go(v1,opi+1,m-1)&go(v2,opi+1,m-1)&go(v3,opi+1,m-1);

            if(res){
                ok = true;
                op[u] = opi;
                for(auto v : {v1,v2,v3}){
                    ll x = new_node(v);
                    adj[u].pb(x);
                    q.push({v,opi+1,m-1,x});                  
                }

                break;
            }            
        }
    }
}

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

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

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

        vector<ll> want = {5,4,1,2,6,3};
        assert(count(all(a),want));

        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{
            assert(0);
        }

        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 'void init(int)':
scales.cpp:170:15: warning: declaration of 'a' shadows a previous local [-Wshadow]
  170 |         auto [a,ind,m,u] = q.front();
      |               ^
scales.cpp:146:16: note: shadowed declaration is here
  146 |     vector<ll> a(n);
      |                ^
scales.cpp:175:14: warning: declaration of 'ok' shadows a previous local [-Wshadow]
  175 |         bool ok = false;
      |              ^~
scales.cpp:155:10: note: shadowed declaration is here
  155 |     bool ok = go(perms,0,7);
      |          ^~
scales.cpp:177:23: warning: conversion from 'std::tuple_element<0, std::tuple<long long int, long long int, long long int> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  177 |         for(int opi = ind; opi < sz(ops); ++opi){
      |                       ^~~
scales.cpp:175:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  175 |         bool ok = false;
      |              ^~
scales.cpp:155:10: warning: unused variable 'ok' [-Wunused-variable]
  155 |     bool ok = go(perms,0,7);
      |          ^~
scales.cpp:127:15: warning: unused parameter 'T' [-Wunused-parameter]
  127 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:257:31: warning: conversion from 'std::tuple_element<0, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  257 |             res = getLightest(i,j,k);
      |                               ^
scales.cpp:257:33: warning: conversion from 'std::tuple_element<1, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  257 |             res = getLightest(i,j,k);
      |                                 ^
scales.cpp:257:35: warning: conversion from 'std::tuple_element<2, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  257 |             res = getLightest(i,j,k);
      |                                   ^
scales.cpp:260:29: warning: conversion from 'std::tuple_element<0, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  260 |             res = getMedian(i,j,k);
      |                             ^
scales.cpp:260:31: warning: conversion from 'std::tuple_element<1, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  260 |             res = getMedian(i,j,k);
      |                               ^
scales.cpp:260:33: warning: conversion from 'std::tuple_element<2, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  260 |             res = getMedian(i,j,k);
      |                                 ^
scales.cpp:263:31: warning: conversion from 'std::tuple_element<0, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  263 |             res = getHeaviest(i,j,k);
      |                               ^
scales.cpp:263:33: warning: conversion from 'std::tuple_element<1, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  263 |             res = getHeaviest(i,j,k);
      |                                 ^
scales.cpp:263:35: warning: conversion from 'std::tuple_element<2, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  263 |             res = getHeaviest(i,j,k);
      |                                   ^

• Subtask 1: 0 / 100