oj.uz

Submission #130336

# Submission time Handle Problem Language Result Execution time Memory
130336 2019-07-14T20:35:43 Z hamzqq9 Scales (IOI15_scales) C++14
100 / 100
 88 ms 1024 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) {

	srand(time(NULL));

	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++) {

					if(i==l || j==l || k==l) continue ;

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

				}

			}

		}

	}

	random_shuffle(all(qs));

	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:202:12: warning: conversion to 'unsigned int' from 'time_t {aka long int}' may alter its value [-Wconversion]
  srand(time(NULL));
        ~~~~^~~~~~
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 72 ms 888 KB Output is correct
2 Correct 73 ms 1016 KB Output is correct
3 Correct 74 ms 1016 KB Output is correct
4 Correct 72 ms 888 KB Output is correct
5 Correct 72 ms 1016 KB Output is correct
6 Correct 72 ms 1016 KB Output is correct
7 Correct 46 ms 888 KB Output is correct
8 Correct 46 ms 1016 KB Output is correct
9 Correct 46 ms 1024 KB Output is correct
10 Correct 46 ms 936 KB Output is correct
11 Correct 46 ms 1020 KB Output is correct
12 Correct 46 ms 1016 KB Output is correct
13 Correct 46 ms 888 KB Output is correct
14 Correct 46 ms 888 KB Output is correct
15 Correct 55 ms 888 KB Output is correct
16 Correct 55 ms 1016 KB Output is correct
17 Correct 55 ms 1016 KB Output is correct
18 Correct 55 ms 1016 KB Output is correct
19 Correct 55 ms 1016 KB Output is correct
20 Correct 56 ms 888 KB Output is correct
21 Correct 55 ms 888 KB Output is correct
22 Correct 57 ms 1016 KB Output is correct
23 Correct 33 ms 888 KB Output is correct
24 Correct 33 ms 1016 KB Output is correct
25 Correct 34 ms 1016 KB Output is correct
26 Correct 34 ms 1016 KB Output is correct
27 Correct 34 ms 1020 KB Output is correct
28 Correct 33 ms 1016 KB Output is correct
29 Correct 34 ms 1016 KB Output is correct
30 Correct 34 ms 1016 KB Output is correct
31 Correct 46 ms 1016 KB Output is correct
32 Correct 33 ms 1016 KB Output is correct
33 Correct 87 ms 1016 KB Output is correct
34 Correct 88 ms 888 KB Output is correct
35 Correct 87 ms 892 KB Output is correct
36 Correct 87 ms 888 KB Output is correct
37 Correct 88 ms 976 KB Output is correct
38 Correct 88 ms 888 KB Output is correct
39 Correct 60 ms 1016 KB Output is correct
40 Correct 60 ms 888 KB Output is correct