Submission #1236083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236083		Nurislam	Scales (IOI15_scales)	C++20	71.43 / 100	860 ms	584 KiB

scales

#include "scales.h"

#include <bits/stdc++.h>

using namespace std;

int inf = 100;

vector<vector<int>> pr;
vector<pair<int,vector<int>> > op;

void init(int T){
	
	/*
	function<int(int, vector<vector<int>>) > rec = [&](int ps, vector<vector<int>> left) {
		if(ps == 6 && left.size() == 1) return 0;
		if(ps == 6 && left.size() != 1) return inf;
		
		for(int i = 0; i < op.size(); i ++ ) {
			if(us[i] == 1) continue;
			us[i] = 1;
			
			vector<vector<vector<int>>> ans(7);
			for(auto & i : left) {
				if()
			};
		};
	};
	*/
};

int gl(vector<int> r) {
	//cout << "L: "  << r[0] << ' ' << r[1] << ' ' << r[2] << '\n';
	return getLightest(r[0], r[1], r[2]);
};
int gh(vector<int> r) {
	//cout << "H: "  << r[0] << ' ' << r[1] << ' ' << r[2] << '\n';
	return getHeaviest(r[0], r[1], r[2]);
};
int gm(vector<int> r) {
	//cout << "M: "  << r[0] << ' ' << r[1] << ' ' << r[2] << '\n';
	return getMedian(r[0], r[1], r[2]);
};
int gn(vector<int> r) {
	return getNextLightest(r[0], r[1], r[2], r[3]);
};
void as(vector<int> ans) {
	int a[6];
	for(int i = 0; i < 6; i ++ ) a[i] = ans[i];
	answer(a);
};

void orderCoins() {
	
	vector<int> p(6);
	iota(p.begin(), p.end(), 1);
	
	set< pair<int,vector<int>> > op2;
	do {
		pr.push_back(p);
		
		vector<int> a;
		for(int i = 1; i < 4; i ++ ) a.push_back(p[i]);
		sort(a.begin(), a.end());
		
		//for(int &i : a)i--;
		
		//op2.insert({0, {p[0], a[0], a[1], a[2]}});
		op2.insert({1, a});
		op2.insert({2, a});
		op2.insert({3, a});
		
	}while(next_permutation(p.begin(),p.end()));
	
	for(auto x : op2)op.push_back(x);
	
	vector<int> us(op.size());
	while(pr.size() > 1) {
		int mx = pr.size();
		int ans;
		for(int i = 0; i < (int)op.size(); i ++ )
		{
			if(us[i])continue;
			auto &o = op[i];
			
			int a = 0, b = 0, c = 0;
			for( auto p : pr){
				vector<int> r;
				for(int j : p) {
					if(j == o.second[0] || j == o.second[1] || j == o.second[2])
						r.push_back(j);
					
				};
				if(o.first == 1) {
					if(r[0] == o.second[0]) a ++ ;
					if(r[0] == o.second[1]) b ++ ;
					if(r[0] == o.second[2]) c ++ ;
				};
				if(o.first == 2) {
					if(r[2] == o.second[0]) a ++ ;
					if(r[2] == o.second[1]) b ++ ;
					if(r[2] == o.second[2]) c ++ ;
				};
				if(o.first == 3) {
					if(r[1] == o.second[0]) a ++ ;
					if(r[1] == o.second[1]) b ++ ;
					if(r[1] == o.second[2]) c ++ ;
				};
			
				//if(o.first == 1){
					//if(p[o.second[0]] < p[o.second[1]] and p[o.second[0]] < p[o.second[2]])
						//a++;
					//else if(p[o.second[1]] < p[o.second[2]])
						//b++;
					//else
						//c++;
					
				//}
				//if(o.first == 2) {
					//if(p[o.second[0]] > p[o.second[1]] and p[o.second[0]] > p[o.second[2]])
						//a++;
					//else if(p[o.second[1]] > p[o.second[2]])
						//b++;
					//else
						//c++;
				//}
				//if(o.first == 3) {
					//if((p[o.second[0]] > p[o.second[1]] and p[o.second[0]] < p[o.second[2]]) or (p[o.second[0]] > p[o.second[2]] and p[o.second[0]] < p[o.second[1]]))
						//a++;
					//else if((p[o.second[1]] > p[o.second[0]] and p[o.second[1]] < p[o.second[2]]) or (p[o.second[1]] > p[o.second[2]] and p[o.second[1]] < p[o.second[0]]))
						//b++;
					//else
						//c++;
				//};
			}
			
			if(mx > max(a, max(b,c))){
				mx = max(a, max(b,c));
				ans = i;
			}
		}
		if(op[ans].first == 1){
			int q = gl(op[ans].second);
			vector<vector<int>> np;
			
			for(auto i : pr) {
				vector<int> r;
				for(int j : i) {
					if(j == op[ans].second[0] || j == op[ans].second[1] || j == op[ans].second[2])
						r.push_back(j);
				};
				if(r[0] == q) {
					np.push_back(i);
				};
			};
			pr = np;
		}
		
		if(op[ans].first == 2){
			int q = gh(op[ans].second);
			vector<vector<int>> np;
			
			
			for(auto i : pr) {
				vector<int> r;
				for(int j : i) {
					if(j == op[ans].second[0] || j == op[ans].second[1] || j == op[ans].second[2])
						r.push_back(j);
				};
				if(r[2] == q) {
					np.push_back(i);
				};
			}
					
			pr = np;
		}
		
		if(op[ans].first == 3){
			int q = gm(op[ans].second);
			vector<vector<int>> np;
			
			for(auto i : pr){
				vector<int> r;
				for(int j : i) {
					if(j == op[ans].second[0] || j == op[ans].second[1] || j == op[ans].second[2])
						r.push_back(j);
				};
				if(r[1] == q) {
					np.push_back(i);
				};
			}
			pr = np;
		}
		//cout << pr.size() << '\n';
		us[ans] = 1;
	}
	as(pr[0]);
};

• Subtask 1: 71.4286 / 100