#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 += cnt[z] * 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 | }
| ^| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
