oj.uz

Submission #130334

# Submission time Handle Problem Language Result Execution time Memory
130334 2019-07-14T20:32:40 Z hamzqq9 Scales (IOI15_scales) C++14
100 / 100
 263 ms 1272 KB 
#include "scales.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define inf 1000000000
#define MOD 1000000007 
#define M 20000000
#define LOG 20
#define KOK 300
#define EPS 0.0000001
using namespace std;

struct query {

	int t;
	vector<int> inds;

};

struct node {

	vector<int> ch;
	query ask;

} T[10000];

int root,tot;
int perm[10000];
vector<vector<int>> ps;
int req[]={243,81,27,9,3,1};
vector<query> qs;

int Light(int who,query ask) {

	if(ps[who][ask.inds[0]]<ps[who][ask.inds[1]] && ps[who][ask.inds[0]]<ps[who][ask.inds[2]]) return 0;
	if(ps[who][ask.inds[1]]<ps[who][ask.inds[0]] && ps[who][ask.inds[1]]<ps[who][ask.inds[2]]) return 1;

	return 2;	

}

int Heavy(int who,query ask) {

	if(ps[who][ask.inds[0]]>ps[who][ask.inds[1]] && ps[who][ask.inds[0]]>ps[who][ask.inds[2]]) return 0;
	if(ps[who][ask.inds[1]]>ps[who][ask.inds[0]] && ps[who][ask.inds[1]]>ps[who][ask.inds[2]]) return 1;

	return 2;	

}

int Median(int who,query ask) {

	int ok[3]={0};

	ok[Light(who,ask)]=1;
	ok[Heavy(who,ask)]=1;

	for(int i=0;i<3;i++) {

		if(!ok[i]) return i;

	}

}

int Next(int who,query ask) {

	int lg;
	int md;
	int hv;

	if(ps[who][ask.inds[3]]<ps[who][ask.inds[lg=Light(who,ask)]]) return lg;
	if(ps[who][ask.inds[3]]<ps[who][ask.inds[md=Median(who,ask)]]) return md;
	if(ps[who][ask.inds[3]]<ps[who][ask.inds[hv=Heavy(who,ask)]]) return hv;

	return lg;

}

int eval(int who,query ask) {

	if(ask.t==0) return Heavy(who,ask);
	if(ask.t==1) return Light(who,ask);
	if(ask.t==2) return Median(who,ask);

	return Next(who,ask);

}

vector<int> get(int root) {

	if(T[root].ch.empty()) return ps[perm[root]];

	int id;
	int t=T[root].ask.t;
	vector<int> inds=T[root].ask.inds;

	if(t==0) id=getHeaviest(inds[0]+1,inds[1]+1,inds[2]+1);
	if(t==1) id=getLightest(inds[0]+1,inds[1]+1,inds[2]+1);
	if(t==2) id=getMedian(inds[0]+1,inds[1]+1,inds[2]+1);
	if(t==3) id=getNextLightest(inds[0]+1,inds[1]+1,inds[2]+1,inds[3]+1);

	for(int i=0;i<sz(inds);i++) {

		if(inds[i]==id-1) {

			return get(T[root].ch[i]);

		}

	}

	assert(0);

}

int mxh;

int build(vector<int> ind,int h) { 

	umax(mxh,h);

	if(sz(ind)<=1) {
		
		++tot;

		if(sz(ind)) perm[tot]=ind[0];

		return tot;

	}

	for(int i=0;i<sz(qs);i++) {

		query ask=qs[i];

		vector<int> branch[3];

		for(auto cur:ind) {

			int res=eval(cur,ask);

			branch[res].pb(cur);

		}

		bool flag=1;

		for(int j=0;j<3;j++) {

			flag&=(sz(branch[j])<=req[h]);

		}

		if(!flag) continue ;

		int bef=tot;

		vector<int> roots;

		for(int j=0;j<3 && flag;j++) {

			roots.pb(build(branch[j],h+1));

			flag&=(roots.back()!=-1);

		}

		if(!flag) {

			tot=bef;

			continue ;

		}

		T[++tot]={roots,ask};

		return tot;

	}

	return -1;

}

void init(int T) {

	vector<int> p;
	vector<int> ind;

	for(int i=1;i<=6;i++) p.pb(i);

	do {

		ps.pb(p);

	} while(next_permutation(all(p)));

	for(int i=0;i<720;i++) ind.pb(i);

	for(int i=0;i<6;i++) {

		for(int j=i+1;j<6;j++) {

			for(int k=j+1;k<6;k++) {

				for(int t=0;t<3;t++) {

					qs.pb({t,{i,j,k}});

				}

				for(int l=0;l<6;l++) {

					qs.pb({3,{i,j,k,l}});

				}

			}

		}

	}

	root=build(ind,0);

}

void orderCoins() {
   	
   	int W[6];

   	vector<int> res=get(root);

   	for(int i=0;i<6;i++) W[res[i]-1]=i+1;

   	answer(W);

}

Compilation message

scales.cpp: In function 'std::vector<int> get(int)':
scales.cpp:103:25: warning: declaration of 'root' shadows a global declaration [-Wshadow]
 vector<int> get(int root) {
                         ^
scales.cpp:40:5: note: shadowed declaration is here
 int root,tot;
     ^~~~
scales.cpp: In function 'void init(int)':
scales.cpp:200:16: warning: declaration of 'T' shadows a global declaration [-Wshadow]
 void init(int T) {
                ^
scales.cpp:38:3: note: shadowed declaration is here
 } T[10000];
   ^
scales.cpp:200:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^
scales.cpp: In function 'int Median(int, query)':
scales.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
scales.cpp: In function 'std::vector<int> get(int)':
scales.cpp:118:17: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(inds[i]==id-1) {
               ~~^~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 1016 KB Output is correct
2 Correct 239 ms 1016 KB Output is correct
3 Correct 240 ms 1016 KB Output is correct
4 Correct 241 ms 1032 KB Output is correct
5 Correct 240 ms 1036 KB Output is correct
6 Correct 240 ms 1000 KB Output is correct
7 Correct 241 ms 1144 KB Output is correct
8 Correct 241 ms 1016 KB Output is correct
9 Correct 241 ms 888 KB Output is correct
10 Correct 239 ms 1016 KB Output is correct
11 Correct 239 ms 1016 KB Output is correct
12 Correct 239 ms 892 KB Output is correct
13 Correct 239 ms 1272 KB Output is correct
14 Correct 238 ms 992 KB Output is correct
15 Correct 238 ms 888 KB Output is correct
16 Correct 239 ms 1016 KB Output is correct
17 Correct 239 ms 1016 KB Output is correct
18 Correct 240 ms 1120 KB Output is correct
19 Correct 245 ms 1000 KB Output is correct
20 Correct 243 ms 996 KB Output is correct
21 Correct 241 ms 1116 KB Output is correct
22 Correct 247 ms 884 KB Output is correct
23 Correct 239 ms 1096 KB Output is correct
24 Correct 242 ms 1040 KB Output is correct
25 Correct 263 ms 1036 KB Output is correct
26 Correct 241 ms 1008 KB Output is correct
27 Correct 244 ms 1124 KB Output is correct
28 Correct 239 ms 888 KB Output is correct
29 Correct 241 ms 1024 KB Output is correct
30 Correct 240 ms 1000 KB Output is correct
31 Correct 239 ms 984 KB Output is correct
32 Correct 239 ms 1024 KB Output is correct
33 Correct 244 ms 1016 KB Output is correct
34 Correct 238 ms 888 KB Output is correct
35 Correct 243 ms 1156 KB Output is correct
36 Correct 238 ms 1016 KB Output is correct
37 Correct 242 ms 1016 KB Output is correct
38 Correct 239 ms 1112 KB Output is correct
39 Correct 239 ms 1016 KB Output is correct
40 Correct 240 ms 1144 KB Output is correct