Submission #1028494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028494		pcc	Scales (IOI15_scales)	C++17	0 / 100	1 ms	436 KiB

scales

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

#define tiii tuple<int,int,int>

const int N = 6;
vector<int> paths[N+1];
int deg[N+1];
vector<tiii> all;

void init(int T) {
	for(int i = 1;i<=N;i++)for(int j = i+1;j<=N;j++)for(int k = j+1;k<=N;k++)all.push_back(tiii(i,j,k));
	return;
}

vector<int> topo(){
	queue<int> q;
	for(int i = 1;i<=N;i++){
		if(!deg[i])q.push(i);
	}
	vector<int> re;
	assert(q.size() == 1);
	while(!q.empty()){
		auto now = q.front();
		q.pop();
		re.push_back(now);
		for(auto nxt:paths[now]){
			deg[nxt]--;
			if(!deg[nxt])q.push(nxt);
		}
	}
	return re;
}

void orderCoins() {
    /* ... */
	srand(time(NULL));
	memset(deg,0,sizeof(deg));
	random_shuffle(all.begin(),all.end());
	int ep = 18;
	while(ep--){
		auto [i,j,k] = all[ep];
		int mx = getHeaviest(i,j,k);
		if(i != mx)deg[i]++,paths[mx].push_back(i);
		if(j != mx)deg[j]++,paths[mx].push_back(j);
		if(k != mx)deg[k]++,paths[mx].push_back(k);
	}
	auto tmp = topo();
	assert(tmp.size() == N);
	int a = tmp.end()[-1],b = tmp.end()[-2];tmp.pop_back();tmp.pop_back();
	if(getLightest(a,b,tmp[0]) == a){
		tmp.push_back(b);
		tmp.push_back(a);
	}
	else{
		tmp.push_back(a);
		tmp.push_back(b);
	}
	reverse(tmp.begin(),tmp.end());
	int ans[N] = {};
	for(int i = 0;i<N;i++)ans[i] = tmp[i];
	answer(ans);
	return;
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:12:15: warning: unused parameter 'T' [-Wunused-parameter]
   12 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:38:12: warning: conversion from 'time_t' {aka 'long int'} to 'unsigned int' may change value [-Wconversion]
   38 |  srand(time(NULL));
      |        ~~~~^~~~~~

• Subtask 1: 0 / 100