Submission #945248

#	Time	Username	Problem	Language	Result	Execution time	Memory
945248		Lobo	Scales (IOI15_scales)	C++17	100 / 100	83 ms	1148 KiB

scales

#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = -1;
vector<vector<int>> allp, queries;
void init(int T) {
    vector<int> p = {0,1,2,3,4,5,6};
    while(p[0] == 0) {
        allp.pb(p);
        next_permutation(all(p));
    }

    for(int a = 1; a <= 6; a++) {
        for(int b = a+1; b <= 6; b++) {
            for(int c = b+1; c <= 6; c++) {
                queries.pb(vector<int>{0,a,b,c});
                queries.pb(vector<int>{1,a,b,c});
                queries.pb(vector<int>{2,a,b,c});
                for(int d = 1; d <= 6; d++) {
                    if(d == a or d == b or d == c) continue;
                    queries.pb(vector<int>{3,a,b,c,d});
                }
            }
        }
    }
    /* ... */
}

// 0 L
// 1 M
// 2 H
// 3 S
// ABC(3->D)
// resp
vector<vector<int>> postot(vector<vector<int>> &disp, vector<int> &vec) {
    vector<vector<int>> ansp;

    for(auto p : disp) {
        bool ok = true;
        int tp = vec[0];
        int res = vec.back();
        if(tp == 0) {
            int a = vec[1];
            int b = vec[2];
            int c = vec[3];

            if(min({p[a],p[b],p[c]}) != p[res]) {
                ok = false;
            }
        }
        else if(tp == 1) {
            int a = vec[1];
            int b = vec[2];
            int c = vec[3];

            if(p[a]+p[b]+p[c] - min({p[a],p[b],p[c]}) - max({p[a],p[b],p[c]}) != p[res]) {
                ok = false;
            }
        }
        else if(tp == 2) {
            int a = vec[1];
            int b = vec[2];
            int c = vec[3];
            if(max({p[a],p[b],p[c]}) != p[res]) {
                ok = false;
            }
        }
        else if(tp == 3) {
            int a = vec[1];
            int b = vec[2];
            int c = vec[3];
            int d = vec[4];

            if(p[d] > max({p[a],p[b],p[c]})) {
                if(p[res] != min({p[a],p[b],p[c]})) {
                    ok = false;
                }
            }
            else {
                int anshere = 7;
                if(p[a] > p[d]) anshere = min(anshere,p[a]);
                if(p[b] > p[d]) anshere = min(anshere,p[b]);
                if(p[c] > p[d]) anshere = min(anshere,p[c]);
                if(anshere != p[res]) {
                    ok = false;
                }
            }
        }

        if(ok) {
            ansp.pb(p);
        }
    }
    return ansp;
}

map<vector<vector<int>>,int> dp;

int sol(vector<vector<int>> ps) {
    if(dp.count(ps)) return dp[ps];
    if(ps.size() == 0) return dp[ps] = 0;
    if(ps.size() == 1) return dp[ps] = 0;

    vector<vector<int>> mns;
    for(auto qr : queries) {
        auto qr1 = qr;
        qr1.pb(0);
        int mx = 0;
        qr1.back() = qr[1];
        mx = max(mx,(int) postot(ps,qr1).size());
        qr1.back() = qr[2];
        mx = max(mx,(int) postot(ps,qr1).size());
        qr1.back() = qr[3];
        mx = max(mx,(int) postot(ps,qr1).size());

        if(mx == ((int) ps.size()+2)/3) {
            mns.pb(qr);
        }
    }
    dp[ps] = 8;
    // random_shuffle(all(mns));

    for(auto qr : mns) {
        auto qr1 = qr;
        qr1.pb(0);
        qr1.back() = qr[1];
        auto p1 = postot(ps,qr1);
        qr1.back() = qr[2];
        auto p2 = postot(ps,qr1);
        qr1.back() = qr[3];
        auto p3 = postot(ps,qr1);

        int mx = max({sol(p1),sol(p2),sol(p3)})+1;
        dp[ps] = min(dp[ps],mx);

        if(ps.size() > 1 && mx == 1) break;
        if(ps.size() > 3 && mx == 2) break;
        if(ps.size() > 9 && mx == 3) break;
        if(ps.size() > 27 && mx == 4) break;
    }
    return dp[ps];
}

void orderCoins() {
    srand(chrono::system_clock::now().time_since_epoch().count());
    vector<vector<int>> perms = allp;
    int resp1;
    while(true) {
        vector<int> qrnew;
        if(perms.size() == 720) {
            qrnew = {1,1,2,3};
        }
        else if(perms.size() == 240) {
            qrnew = {3,4,5,6,(resp1 == 1 ? 2 : 1)};
        }
        else {
            // cout << perms.size() << "  " << sol(perms) << endl;
            vector<vector<int>> mns;
            for(auto qr : queries) {
                auto qr1 = qr;
                qr1.pb(0);
                int mx = 0;
                qr1.back() = qr[1];
                auto p1 = postot(perms,qr1);
                qr1.back() = qr[2];
                auto p2 = postot(perms,qr1);
                qr1.back() = qr[3];
                auto p3 = postot(perms,qr1);
                mx = max({p1.size(),p2.size(),p3.size()});

                if(mx == ((int) perms.size()+2)/3) {
                    mns.pb(qr);
                }
            }
            // cout << mns.size() << endl;
            // random_shuffle(all(mns));

            for(auto qr : mns) {
                auto qr1 = qr;
                qr1.pb(0);
                qr1.back() = qr[1];
                auto p1 = postot(perms,qr1);
                qr1.back() = qr[2];
                auto p2 = postot(perms,qr1);
                qr1.back() = qr[3];
                auto p3 = postot(perms,qr1);

                int mx = max({sol(p1),sol(p2),sol(p3)})+1;
                qrnew = qr;
                if(perms.size() > 1 && mx == 1) break;
                if(perms.size() > 3 && mx == 2) break;
                if(perms.size() > 9 && mx == 3) break;
                if(perms.size() > 27 && mx == 4) break;
            }
        }

        auto qr = qrnew;

        if(qr[0] == 0) {
            qr.pb(getLightest(qr[1],qr[2],qr[3]));
        }
        if(qr[0] == 1) {
            qr.pb(getMedian(qr[1],qr[2],qr[3]));
        }
        if(qr[0] == 2) {
            qr.pb(getHeaviest(qr[1],qr[2],qr[3]));
        }
        if(qr[0] == 3) {
            qr.pb(getNextLightest(qr[1],qr[2],qr[3],qr[4]));
        }

        if(perms.size() == 720) {
            resp1 = qr.back();
        }

        

        // cout << " " << perms.size() << endl;
        // for(auto x : qr) cout << x << endl;
        // cout << endl;
        // cout << mnqr.fr << endl;

        // cout << " " << postot(perms,qrsofar).size() << endl;
        // auto p = postot(perms,qrsofar)[0];
        // for(int i = 1; i <= 6; i++) cout << p[i] << " "; cout << endl;
        // p = postot(perms,qrsofar)[1];
        // for(int i = 1; i <= 6; i++) cout << p[i] << " "; cout << endl;


        perms = postot(perms,qr);
        // cout << perms.size() << endl;

        if(perms.size() == 1) break;
    }

    auto p = perms[0];
    vector<int> pos(7);
    for(int i = 1; i <= 6; i++) pos[p[i]] = i;


    auto ansvec = pos;
    int ANS[] = {ansvec[1],ansvec[2],ansvec[3],ansvec[4],ansvec[5],ansvec[6]};

    answer(ANS);

    // /* ... */
    // int W[] = {1, 2, 3, 4, 5, 6};
    // answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:12:15: warning: unused parameter 'T' [-Wunused-parameter]
   12 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:151:63: warning: conversion from 'std::chrono::duration<long int, std::ratio<1, 1000000000> >::rep' {aka 'long int'} to 'unsigned int' may change value [-Wconversion]
  151 |     srand(chrono::system_clock::now().time_since_epoch().count());
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
scales.cpp:175:25: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
  175 |                 mx = max({p1.size(),p2.size(),p3.size()});
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:160:42: warning: 'resp1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  160 |             qrnew = {3,4,5,6,(resp1 == 1 ? 2 : 1)};
      |                              ~~~~~~~~~~~~^~~~~~~~

• Subtask 1: 100 / 100