Submission #756752

#	Time	Username	Problem	Language	Result	Execution time	Memory
756752		minhcool	Scales (IOI15_scales)	C++17	0 / 100	28 ms	724 KiB

scales

//#define local
#ifndef local
#include "scales.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
mt19937 rng(1);
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
int cnt;
int nxt[N][3];
 
int endd[N];
 
int perm[721][7];
 
struct ope{
	int type;
	int a, b, c, d;
	ope(){}
	ope(int _type, int _a, int _b, int _c): type(_type), a(_a), b(_b), c(_c){}
	ope(int _type, int _a, int _b, int _c, int _d): type(_type), a(_a), b(_b), c(_c), d(_d){}
};
 
ope todo[N];
vector<ope> opes;
 
bool bt(int node, vector<int> index){
//	cout << node << " " << index.size();
//	cout << "\n";
	if(index.size() <= 1){
		if(index.size() == 1) endd[node] = index[0];
		return 1;
	}
	int sz = (index.size() + 1) / 3;
//	iii arr;
//	int type;
	for(auto it : opes){
		vector<int> v1, v2, v3;
		for(auto it2 : index){
			if(it.type == 1){// maximum
				int temp = max({perm[it2][it.a], perm[it2][it.b], perm[it2][it.c]});
				if(perm[it2][it.a] == temp) v1.pb(it2);
				else if(perm[it2][it.b] == temp) v2.pb(it2);
				else v3.pb(it2);
			}
			else if(it.type == 2){//median 
				int temp = max({perm[it2][it.a], perm[it2][it.b], perm[it2][it.c]}) + min({perm[it2][it.a], perm[it2][it.b], perm[it2][it.c]});
				temp = perm[it2][it.a] + perm[it2][it.b] + perm[it2][it.c] - temp;
				if(perm[it2][it.a] == temp) v1.pb(it2);
				else if(perm[it2][it.b] == temp) v2.pb(it2);
				else v3.pb(it2);
			}
			else if(it.type == 3){// minimum
				int temp = min({perm[it2][it.a], perm[it2][it.b], perm[it2][it.c]});
				if(perm[it2][it.a] == temp) v1.pb(it2);
				else if(perm[it2][it.b] == temp) v2.pb(it2);
				else v3.pb(it2);
			}
			else{
				int temp = max({perm[it2][it.a], perm[it2][it.b], perm[it2][it.c]});
				if(temp < perm[it2][it.d]){
					temp = min({perm[it2][it.a], perm[it2][it.b], perm[it2][it.c]});
					if(perm[it2][it.a] == temp) v1.pb(it2);
					else if(perm[it2][it.b] == temp) v2.pb(it2);
					else v3.pb(it2);
				}
				else{
					if(perm[it2][it.a] > perm[it2][it.d] && perm[it2][it.a] < temp) temp = perm[it2][it.a];
					if(perm[it2][it.b] > perm[it2][it.d] && perm[it2][it.b] < temp) temp = perm[it2][it.b];
					if(perm[it2][it.c] > perm[it2][it.d] && perm[it2][it.c] < temp) temp = perm[it2][it.c];
					if(perm[it2][it.a] == temp) v1.pb(it2);
					else if(perm[it2][it.b] == temp) v2.pb(it2);
					else v3.pb(it2);
				}
			}
		}
		if(max({v1.size(), v2.size(), v3.size()}) > sz) continue;
		todo[node] = it;
		for(int i = 0; i < 3; i++){
			cnt++;
			nxt[node][i] = cnt;
		}
		bool temp = 1;
		temp &= bt(cnt - 2, v1);
		temp &= bt(cnt - 1, v2);
		temp &= bt(cnt, v3);
	//	break;
		if(temp) return 1;
	}
	return 0;
}
 
void init(int tt){
	int arr[7];
	for(int i = 1; i <= 6; i++) arr[i] = i;
	int t = 0;
	vector<int> per;
	do{
		t++;
		for(int i = 1; i <= 6; i++) perm[t][i] = arr[i];
		per.pb(t);
//		for(int i = 1; i <= 6; i++) cout << arr[i] << " ";
//		cout << "\n";
	}while(next_permutation(arr + 1, arr + 7));
	for(int i = 1; i <= 6; i++){
		for(int j = i + 1; j <= 6; j++){
			for(int k = j + 1; k <= 6; k++){
				for(int h = 1; h <= 3; h++) opes.pb({h, i, j, k});
				for(int h = 1; h <= 6; h++){
					if(h == i || h == j || h == k) continue;
					opes.pb({4, i, j, k, h});
				}
			}
		}
	}
	bt(1, per);
	//cout << bt(1, per) << "\n";
}
 
void orderCoins(){
	int itr = 1;
	while(1){
		if(endd[itr]){
			int arr[6];
			for(int i = 1; i <= 6; i++) arr[i - 1] = perm[endd[itr]][i];
			answer(arr);
			return;
		}
		if(todo[itr].type == 1){
			int t = getHeaviest(todo[itr].a, todo[itr].b, todo[itr].c);
			if(t == todo[itr].a) itr = nxt[itr][0];
			else if(t == todo[itr].b) itr = nxt[itr][1];
			else itr = nxt[itr][2];
		}
		else if(todo[itr].type == 2){
			int t = getMedian(todo[itr].a, todo[itr].b, todo[itr].c);
			if(t == todo[itr].a) itr = nxt[itr][0];
			else if(t == todo[itr].b) itr = nxt[itr][1];
			else itr = nxt[itr][2];
		}
		else if(todo[itr].type == 3){
			int t = getLightest(todo[itr].a, todo[itr].b, todo[itr].c);
			if(t == todo[itr].a) itr = nxt[itr][0];
			else if(t == todo[itr].b) itr = nxt[itr][1];
			else itr = nxt[itr][2];	
		}
		else{
			int t = getNextLightest(todo[itr].a, todo[itr].b, todo[itr].c, todo[itr].d);
			if(t == todo[itr].a) itr = nxt[itr][0];
			else if(t == todo[itr].b) itr = nxt[itr][1];
			else itr = nxt[itr][2];	
		}
	}
}
 
//#define local
#ifdef local
void process(){
	init(1);
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
	/*
	int t;
	cin >> t;
	while(t--) process();*/
}
#endif

Compilation message (stderr)

scales.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
scales.cpp: In function 'int rnd(int, int)':
scales.cpp:27:19: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   27 |  int temp = rng() % (r - l + 1);
      |             ~~~~~~^~~~~~~~~~~~~
scales.cpp: In function 'bool bt(int, std::vector<int>)':
scales.cpp:56:30: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   56 |  int sz = (index.size() + 1) / 3;
      |           ~~~~~~~~~~~~~~~~~~~^~~
scales.cpp:99:45: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
   99 |   if(max({v1.size(), v2.size(), v3.size()}) > sz) continue;
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
scales.cpp: In function 'void init(int)':
scales.cpp:115:15: warning: unused parameter 'tt' [-Wunused-parameter]
  115 | void init(int tt){
      |           ~~~~^~

• Subtask 1: 0 / 100