Submission #706170

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
706170	2023-03-06T03:39:17 Z	SamNguyen	Scales (IOI15_scales)	C++14	6.4343 / 100	1 ms	304 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1 ms	212 KB	Output is partially correct
2	Partially correct	0 ms	212 KB	Output is partially correct
3	Partially correct	0 ms	212 KB	Output is partially correct
4	Partially correct	0 ms	212 KB	Output is partially correct
5	Partially correct	1 ms	212 KB	Output is partially correct
6	Partially correct	1 ms	212 KB	Output is partially correct
7	Partially correct	1 ms	212 KB	Output is partially correct
8	Partially correct	1 ms	304 KB	Output is partially correct
9	Partially correct	0 ms	212 KB	Output is partially correct
10	Partially correct	1 ms	212 KB	Output is partially correct
11	Partially correct	1 ms	212 KB	Output is partially correct
12	Partially correct	1 ms	212 KB	Output is partially correct
13	Partially correct	1 ms	212 KB	Output is partially correct
14	Partially correct	0 ms	212 KB	Output is partially correct
15	Partially correct	1 ms	212 KB	Output is partially correct
16	Partially correct	0 ms	212 KB	Output is partially correct
17	Partially correct	0 ms	212 KB	Output is partially correct
18	Partially correct	0 ms	212 KB	Output is partially correct
19	Partially correct	1 ms	212 KB	Output is partially correct
20	Partially correct	0 ms	212 KB	Output is partially correct
21	Partially correct	0 ms	212 KB	Output is partially correct
22	Partially correct	1 ms	212 KB	Output is partially correct
23	Partially correct	1 ms	212 KB	Output is partially correct
24	Partially correct	0 ms	212 KB	Output is partially correct
25	Partially correct	1 ms	212 KB	Output is partially correct
26	Partially correct	0 ms	212 KB	Output is partially correct
27	Partially correct	1 ms	212 KB	Output is partially correct
28	Partially correct	1 ms	212 KB	Output is partially correct
29	Partially correct	1 ms	212 KB	Output is partially correct
30	Partially correct	1 ms	212 KB	Output is partially correct
31	Partially correct	1 ms	212 KB	Output is partially correct
32	Partially correct	1 ms	212 KB	Output is partially correct
33	Partially correct	1 ms	212 KB	Output is partially correct
34	Partially correct	1 ms	212 KB	Output is partially correct
35	Partially correct	1 ms	212 KB	Output is partially correct
36	Partially correct	1 ms	212 KB	Output is partially correct
37	Partially correct	1 ms	212 KB	Output is partially correct
38	Partially correct	0 ms	212 KB	Output is partially correct
39	Partially correct	0 ms	212 KB	Output is partially correct
40	Partially correct	0 ms	212 KB	Output is partially correct