Submission #1028542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028542		pcc	Scales (IOI15_scales)	C++17	0 / 100	1091 ms	48232 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;

#define tiii tuple<int,int,int>
#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 1e6+10;
const int N = 6;
int tp[mxn];
vector<pii> tree[mxn];
int pw[N+1];
int ep = 0;
const int lim = 10000;

int encode(vector<int> v){
	assert(v.size() == N);
	int re = 0;
	for(int i = 0;i<v.size();i++){
		re += v[i]*pw[i];
	}
	return re;
}
vector<int> decode(int k){
	vector<int> re(N);
	for(int i = 0;i<N;i++){
		re[i] = k%N;
		k/=N;
	}
	return re;
}

namespace TREE{
	vector<int> cases;
	vector<int> param[mxn];
	vector<int> op;
	bitset<mxn> done;
	void init(){
		int pt = 0;
		for(int i = 0;i<N;i++){
			for(int j = i+1;j<=N;j++){
				for(int k = j+1;k<=N;k++){
					param[pt] = {i,j,k,1};
					op.push_back(pt);
					pt++;
					param[pt] = {i,j,k,2};
					op.push_back(pt);
					pt++;
					param[pt] = {i,j,k,3};
					op.push_back(pt);
					pt++;
					for(int l = 0;l<N;l++){
						if(l == i||l == j||l == k)continue;
						param[pt] = {i,j,k,l,4};
						op.push_back(pt);
						pt++;
					}
				}
			}
		}
		//cerr<<"OPS: "<<op.size()<<endl;
		vector<int> perm(N);for(int i = 0;i<N;i++)perm[i] = i;
		do{
			cases.push_back(encode(perm));
		}while(next_permutation(perm.begin(),perm.end()));
		//cerr<<"CASES: "<<cases.size()<<endl;
		return;
	}
	int f(int opid,int val){
		auto v = param[opid];
		auto arr = decode(val);
		sort(v.begin(),v.begin()+3,[&](int a,int b){return arr[a]<arr[b];});
		if(v.back() == 1)return v[2];
		else if(v.back() == 2)return v[0];
		else if(v.back() == 3)return v[1];
		else{
			for(int i = 0;i<3;i++)if(arr[v[i]]>arr[v[3]])return v[i];
			return v[0];
		}
	}
	vector<pair<int,vector<int>>> part(int opid,vector<int> &v){
		vector<pair<int,vector<int>>> re;
		for(int i = 0;i<v.size();i++){
			int val = f(opid,v[i]);
			bool gp = false;
			for(auto &j:re){
				if(j.fs == val)gp = true,j.sc.push_back(v[i]);
			}
			if(!gp)re.push_back(make_pair(val,vector<int>(1,v[i])));
		}
		return re;
	}
	int vcnt = 0;
	int newnode(){
		tree[vcnt].clear();
		return vcnt++;
	}
	bool dfs(vector<int> &v,int dep,int nodeid){//false if fails
		if(v.size() == 1){
			tp[nodeid] = v[0];
			return true;
		}
		if(dep>=8)return false;
		ep++;
		//if(ep%lim == 0)cout<<ep<<" tries"<<','<<nodeid<<endl;
		//cerr<<nodeid<<":"<<dep<<','<<v.size()<<endl;
		for(auto &opid:op){
			if(done[opid])continue;
			auto arr = part(opid,v);
			int sum = 0;
			bool flag = true;
			for(auto &i:arr)sum += i.sc.size();
			for(auto &i:arr){
				//if(sum>10&&sum-i.sc.size()<=5)flag = false;
				if(sum == i.sc.size())flag = false;
			}
			if(!flag)continue;
			done[opid] = true;
			tp[nodeid] = opid;
			for(auto &i:arr){
				tree[nodeid].push_back(pii(i.fs,newnode()));
				flag = flag&&dfs(i.sc,dep+1,tree[nodeid].back().sc);
				if(!flag)break;
			}
			done[opid] = false;
			if(flag)return true;
			tp[nodeid] = -1;
		}
		while(vcnt>nodeid){
			vcnt--;
			tree[vcnt].clear();
		}
		vcnt = nodeid;
		return false;
	}
	void GO(){
		init();
		dfs(cases,0,newnode());
		//cerr<<"TREE DONE!: "<<vcnt<<endl;
		for(int i = 0;i<vcnt;i++)cout<<tp[i]<<' ';cout<<endl;
		cout<<"EDGES: "<<endl;
		for(int i = 0;i<vcnt;i++){
			for(auto nxt:tree[i])cout<<i<<' '<<nxt.fs<<' '<<nxt.sc<<endl;
			if(tree[i].empty()){
				auto arr = decode(tp[i]);
				//cerr<<i<<": ";for(auto &i:arr)cerr<<i<<' ';cerr<<endl;
			}
		}
		return;
	}
}

void init(int T) {
	pw[0] = 1;
	for(int i = 1;i<=N;i++)pw[i] = pw[i-1]*N;
	TREE::GO();
}

void orderCoins() {
    /* ... */
	int ans[N] = {};
	answer(ans);
	return;
}

Compilation message (stderr)

scales.cpp: In function 'int encode(std::vector<int>)':
scales.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i = 0;i<v.size();i++){
      |                ~^~~~~~~~~
scales.cpp: In function 'std::vector<std::pair<int, std::vector<int> > > TREE::part(int, std::vector<int>&)':
scales.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for(int i = 0;i<v.size();i++){
      |                 ~^~~~~~~~~
scales.cpp: In function 'bool TREE::dfs(std::vector<int>&, int, int)':
scales.cpp:114:37: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  114 |    for(auto &i:arr)sum += i.sc.size();
      |                                     ^
scales.cpp:117:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     if(sum == i.sc.size())flag = false;
      |        ~~~~^~~~~~~~~~~~~~
scales.cpp: In function 'void TREE::GO()':
scales.cpp:142:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  142 |   for(int i = 0;i<vcnt;i++)cout<<tp[i]<<' ';cout<<endl;
      |   ^~~
scales.cpp:142:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  142 |   for(int i = 0;i<vcnt;i++)cout<<tp[i]<<' ';cout<<endl;
      |                                             ^~~~
scales.cpp: In function 'void init(int)':
scales.cpp:155:15: warning: unused parameter 'T' [-Wunused-parameter]
  155 | void init(int T) {
      |           ~~~~^

• Subtask 1: 0 / 100