제출 #1325368

#제출 시각아이디문제언어결과실행 시간메모리
1325368minh30082008저울 (IOI15_scales)C++20
71.43 / 100
1 ms412 KiB
#include "scales.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define FOR(i, k, n) for(int i = k; i <= n; i++)
#define FOR1(i, k, n) for(int i = k; i >= n; i--)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
#define re return 0
#define mii map<int, int>
#define input "wtf.inp"
#define output "wtf.out"
#define rf 	freopen(input, "r", stdin); freopen(output, "w", stdout)
using namespace std;
bool vis[10];
int d[10];
vi adj[10];
bool diduoc(int u, int v)
{
	if(u == v)
		return 1;
	for(auto v1 : adj[u])
	{
		if(diduoc(v1, v))
			return 1;
	}
	return 0;
}
void themcanh(int u, int v)
{
	if(diduoc(u, v))
		return;
	adj[u].pb(v);
	d[v]++;
}
void init(int t)
{
	return;
}
int dapan[6];
void orderCoins()
{
	FOR(i, 1, 6)
		vis[i] = d[i] = 0, adj[i].clear();
	int id = getLightest(1, 2, 3);
	FOR(i, 1, 3)
		if(i != id)
			adj[id].pb(i), d[i]++;
	int id1 = getLightest(4, 5, 6);
	FOR(i, 4, 6)
		if(i != id1)
			adj[id1].pb(i), d[i]++;
	vi tmp;
	vi ans;
	while((int)ans.size() < 6)
	{
		tmp.clear();
		FOR(i, 1, 6)
			if(!vis[i] && d[i] == 0)
				tmp.pb(i);
		if(tmp.size() == 1)
		{
			ans.pb(tmp.back());
			vis[tmp.back()] = 1;
			for(auto x : adj[tmp.back()])
				d[x]--;
			continue;
		}
		if((int)tmp.size() == 2)
		{
			id = tmp[0];
			id1 = tmp[1];
			if(ans.size() == 4)
			{
				int t;
				FOR(i, 1, 6)
					if(vis[i])
						t = i;
				int x = getHeaviest(id, id1, t);
				if(x == id)
					ans.pb(id1), ans.pb(id);
				else
					ans.pb(id), ans.pb(id1);
				break;
			}
			int t;
			FOR(i, 1, 6)
				if(d[i] && !vis[i])
				{
					int res = diduoc(id, i) + diduoc(id1, i);
					t = i;
					if(res == 1)
						break;
				}
			if(diduoc(id, t) < diduoc(id1, t))
				swap(id, id1);
			int x = getMedian(id, t, id1);
			if(x == id)
				themcanh(id1, id);
			if(x == id1)
			{
				themcanh(id, id1);
				themcanh(id1, t);
			}
			if(x == t)
				themcanh(t, id1);
		}
		if((int)tmp.size() >= 3)
		{
			id = getLightest(tmp[0], tmp[1], tmp[2]);
			FOR(i, 0, 2)
				if(id != tmp[i])
					themcanh(id, tmp[i]);
		}
	}
	FOR(i, 0, 5)
		dapan[i] = ans[i];
	answer(dapan);
}
#Verdict Execution timeMemoryGrader output
Fetching results...