Submission #1219405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219405		Zbyszek99	Scales (IOI15_scales)	C++20	71.43 / 100	23 ms	492 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

struct query
{
    int type;
    vi elms;
    int operator()()
    {
        if(type == 0)
        {
            return getHeaviest(elms[0]+1,elms[1]+1,elms[2]+1)-1;
        }
        if(type == 1)
        {
            return getLightest(elms[0]+1,elms[1]+1,elms[2]+1)-1;
        }
        if(type == 2)
        {
            return getMedian(elms[0]+1,elms[1]+1,elms[2]+1)-1;
        }
        if(type == 3)
        {
            return getNextLightest(elms[0]+1,elms[1]+1,elms[2]+1,elms[3]+1)-1;
        }
    }
};

vector<vi> perms;
vector<query> queries;

int get_ans(vi& p, query& q)
{
    int a = p[q.elms[0]];
    int b = p[q.elms[1]];
    int c = p[q.elms[2]];
    if(q.type == 0)
    {
        if(a > b && a > c) return q.elms[0];
        if(b > a && b > c) return q.elms[1];
        return q.elms[2];
    }
    if(q.type == 1)
    {
        if(a < b && a < c) return q.elms[0];
        if(b < a && b < c) return q.elms[1];
        return q.elms[2];
    }
    if(q.type == 2)
    {
        if((a < b && a > c) || (a < c && a > b)) return q.elms[0];
        if((b < a && b > c) || (b < c && b > a)) return q.elms[1];
        return q.elms[2];
    }
    if(q.type == 3)
    {
        pii ans = {1e9,0};
        rep(i,3)
        {
            if(p[q.elms[i]] > p[q.elms[3]])
            {
                ans = min(ans,{p[q.elms[i]],q.elms[i]});
            }
        }
        if(ans.ff != 1e9) return ans.ss;
        if(a < b && a < c) return q.elms[0];
        if(b < a && b < c) return q.elms[1];
        return q.elms[2];
    }
}

void gen_perms(vi cur, vi rest)
{
    if(siz(rest) == 0) 
    {
        perms.pb(cur);
        return;
    }
    rep(i,siz(rest))
    {
        int x = rest[i];
        cur.pb(x);
        swap(rest[i],rest[siz(rest)-1]);
        rest.pop_back();
        gen_perms(cur,rest);
        rest.pb(x);
        swap(rest[i],rest[siz(rest)-1]);
        cur.pop_back();
    }
}

void init(int T) 
{
    gen_perms({},{1,2,3,4,5,6});
    rep2(z1,0,5)
    {
        rep2(z2,z1+1,5)
        {
            rep2(z3,z2+1,5)
            {
                rep(d,3) queries.pb({d,{z1,z2,z3}});
                rep2(z,0,5)
                {
                    if(z != z1 && z != z2 && z != z3)
                    {
                        queries.pb({3,{z1,z2,z3,z}});
                    }
                }
            }
        }
    }
}

vi buckets[7];
int cnt[7];

void gen_tree(vi p)
{
    if(siz(p) == 0) return;
    if(siz(p) == 1)
    {
        int W[] = {0,0,0,0,0,0};
        rep(i,6)
        {
            W[perms[p[0]][i]-1] = i+1;
        }
        answer(W);
        return;
    }
    rep2(i,0,6) buckets[i] = {};
    pii best = {1e9,1e9};
    rep(i,siz(queries))
    {
        rep2(z,0,6) cnt[z] = 0;
        forall(it,p)
        {
            cnt[get_ans(perms[it],queries[i])]++;
        }
        int ans = 0;
        rep2(z,0,6) ans = max(ans,cnt[z]);
        best = min(best,{ans,i});
    }
    forall(it,p)
    {
        buckets[get_ans(perms[it],queries[best.ss])].pb(it);
    }
    int val = queries[best.ss]();
    gen_tree(buckets[val]);
}

void orderCoins() 
{
    vi pom;
    rep(i,siz(perms)) pom.pb(i);
    gen_tree(pom);
}

Compilation message (stderr)

scales.cpp: In function 'int get_ans(std::vector<int>&, query&)':
scales.cpp:97:1: warning: control reaches end of non-void function [-Wreturn-type]
   97 | }
      | ^
scales.cpp: In member function 'int query::operator()()':
scales.cpp:53:5: warning: control reaches end of non-void function [-Wreturn-type]
   53 |     }
      |     ^

• Subtask 1: 71.4286 / 100