Submission #706170

#	Time	Username	Problem	Language	Result	Execution time	Memory
706170		SamNguyen	Scales (IOI15_scales)	C++14	6.43 / 100	1 ms	304 KiB

scales

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

class DAG {
private:
	int n;
	vector<vector<int>> adj;

public:
	DAG(int n): n(n) {
		adj.assign(n + 1, vector<int>());
	}

	inline void add_edge(int u, int v) {
		adj[u].push_back(v);
	}

	vector<int> unique_topo_order() {
		vector<int> deg(n + 1, 0);
		for (int u = 1; u <= n; u++) for (int v : adj[u])
			deg[v]++;

		queue<int> q;
		for (int u = 1; u <= n; u++) if (deg[u] == 0)
			q.push(u);

		if (q.size() > 1)
			return vector<int>();

		vector<int> res;
		while (not q.empty()) {
			int u = q.front(); q.pop();
			res.push_back(u);
			if (int(res.size()) == n)
				break;

			vector<int> nxts;
			for (int v : adj[u]) {
				deg[v]--;
				if (deg[v] == 0)
					nxts.push_back(v);
			}

			if (nxts.size() > 1)
				return vector<int>();

			q.push(nxts.front());
		}

		return res;
	}
};

mt19937 rnd(82394 + time(NULL));

void init(int T) {
}

void orderCoins() {
	DAG dag(6);

	vector<tuple<int, int, int>> inds;
	for (int A = 1; A <= 6; A++)
	for (int B = A + 1; B <= 6; B++)
	for (int C = B + 1; C <= 6; C++)
		inds.emplace_back(A, B, C);

	shuffle(inds.begin(), inds.end(), rnd);

	vector<int> topo;
	while (true) {
		topo = dag.unique_topo_order();
		if (not topo.empty())
			break;
		
		int A, B, C;
		tie(A, B, C) = inds.back();
		inds.pop_back();

		int X = getLightest(A, B, C);
		int Y = getMedian(A, B, C);
		int Z = getHeaviest(A, B, C);

		dag.add_edge(X, Y);
		dag.add_edge(Y, Z);
	}

	int W[5];
	copy(topo.begin(), topo.end(), W);
	answer(W);
}

Compilation message (stderr)

scales.cpp: In constructor 'DAG::DAG(int)':
scales.cpp:11:10: warning: declaration of 'n' shadows a member of 'DAG' [-Wshadow]
   11 |  DAG(int n): n(n) {
      |      ~~~~^
scales.cpp:7:6: note: shadowed declaration is here
    7 |  int n;
      |      ^
scales.cpp: In constructor 'DAG::DAG(int)':
scales.cpp:11:10: warning: declaration of 'n' shadows a member of 'DAG' [-Wshadow]
   11 |  DAG(int n): n(n) {
      |      ~~~~^
scales.cpp:7:6: note: shadowed declaration is here
    7 |  int n;
      |      ^
scales.cpp: In constructor 'DAG::DAG(int)':
scales.cpp:11:10: warning: declaration of 'n' shadows a member of 'DAG' [-Wshadow]
   11 |  DAG(int n): n(n) {
      |      ~~~~^
scales.cpp:7:6: note: shadowed declaration is here
    7 |  int n;
      |      ^
scales.cpp: In function 'void init(int)':
scales.cpp:57:15: warning: unused parameter 'T' [-Wunused-parameter]
   57 | void init(int T) {
      |           ~~~~^

• Subtask 1: 6.434296 / 100