#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;
map<ull,int> real_tree;
vi tree_vals = {2,114,57,58,118,17,9,9,118,3,50,34,118,3,40,44,67,20,52,3,3,54,3,5,16,8,52,5,5,73,14,46,3,3,54,3,22,4,8,46,4,4,51,52,118,15,11,15,118,48,4,28,118,41,4,44,61,20,58,4,4,48,4,5,10,10,58,5,5,73,8,46,4,4,48,4,23,3,14,46,3,3,45,46,118,21,21,10,118,42,29,5,118,35,42,5,61,14,58,5,5,42,5,4,11,11,58,4,4,67,8,52,5,5,42,5,17,3,17,52,3,3,114,35,31,40,4,45,4,11,4,16,45,8,11,3,11,31,57,3,46,46,40,45,4,4,9,51,8,18,27,28,57,40,26,20,8,28,45,4,11,0,18,29,25,41,3,45,3,17,3,10,45,14,17,4,17,25,51,4,46,46,41,45,3,3,15,57,10,18,33,34,51,41,26,20,10,26,45,3,17,0,18,28,25,35,3,51,3,23,3,11,45,17,14,14,21,25,45,5,52,52,35,51,3,3,21,57,11,12,31,80,29,5,52,80,11,5,50,5,18,0,19,114,17,13,22,4,46,4,29,4,34,46,6,52,3,21,13,58,3,45,45,22,46,4,4,6,3,52,21,9,10,58,22,8,10,22,58,8,4,21,21,0,11,7,23,3,46,3,35,3,28,46,12,58,4,21,7,52,4,45,45,23,46,3,3,12,4,58,21,15,16,52,23,8,16,23,52,8,3,21,21,0,10,7,17,3,52,3,41,3,29,46,18,58,5,15,7,46,5,51,51,17,52,3,3,18,5,58,15,13,98,11,5,51,98,11,5,50,5,18,18,0};
ull P[1000001];
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();
}
}
int cur_node = 0;
vi buckets[7];
void gen_tree(vi p)
{
ull H = 0;
forall(it,p)
{
H += P[it];
}
if(siz(p) <= 1) return;
int move = tree_vals[cur_node++];
real_tree[H] = move;
rep2(i,0,6) buckets[i] = {};
vector<vi> perms2;
forall(it,p)
{
buckets[get_ans(perms[it],queries[move])].pb(it);
}
rep2(i,0,6) perms2.pb(buckets[i]);
forall(it,perms2)
{
gen_tree(it);
}
}
void init(int T)
{
P[0] = 1;
rep2(i,1,1000000) P[i] = (P[i-1] * 2137ULL);
random_start();
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 pom;
rep(i,siz(perms)) pom.pb(i);
gen_tree(pom);
}
void gen_ans(vi p)
{
ull H = 0;
forall(it,p)
{
H += P[it];
}
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;
}
int oper = real_tree[H];
rep2(i,0,6) buckets[i] = {};
forall(it,p)
{
buckets[get_ans(perms[it],queries[oper])].pb(it);
}
int val = queries[oper]();
gen_ans(buckets[val]);
}
void orderCoins()
{
vi pom;
rep(i,siz(perms)) pom.pb(i);
gen_ans(pom);
}
컴파일 시 표준 에러 (stderr) 메시지
scales.cpp: In function 'int get_ans(std::vector<int>&, query&)':
scales.cpp:100:1: warning: control reaches end of non-void function [-Wreturn-type]
100 | }
| ^
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... |
