oj.uz

Submission #108024

# Submission time Handle Problem Language Result Execution time Memory
108024 2019-04-26T22:54:16 Z Noam527 Mechanical Doll (IOI18_doll) C++17
100 / 100
 260 ms 18760 KB 
#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 1;
const int OOO = 1;
using namespace std;

void answer(vector<int> C, vector<int> X, vector<int> Y);

struct node {
	int tar, l, r, ind;
	int mode;
	node() {}
	node(int ii) {
		tar = 1;
		ind = ii;
		l = r = md;
		mode = 0;
	}
	node(int ll, int rr, int ii) {
		l = ll;
		r = rr;
		ind = ii;
		tar = 0;
		mode = 0;
	}
	int next() {
		if (mode) return mode ^= 1, r;
		return mode ^= 1, l;
	}
};

int n, m;
vector<node> g;
vector<int> order;

void walk() {
	int v = (int)g.size() - 1;
	while (order.size() < n) {
		if (g[v].tar) {
			order.push_back(v);
			v = (int)g.size() - 2;
		}
		else
			v = g[v].next();
	}
}

void create_circuit(int M, vector<int> A) {
	A.push_back(n);
	n = A.size(), m = M;
	for (int i = 0; i < n; i++)
		g.push_back(node(i));
	int nxt = 0, lst = n - 1;
	int S = 0;
	while (nxt < lst) {
		while (nxt <= lst) {
			g.push_back(node(nxt, (nxt + 1 <= lst ? nxt + 1 : md), -1));
			S++;
			nxt = min(nxt + 2, lst + 1);
		}
		lst = (int)g.size() - 1;
	}
	g.push_back(node(nxt, nxt, -1));
	for (auto &i : g)
		if (i.r == md) i.r = (int)g.size() - 2;
	for (auto &i : g)
		swap(i.l, i.r);
	
	nxt = 0;
	for (int i = (int)g.size() - 1; g[i].tar == 0; i--)
		g[i].ind = nxt++;
	walk();

	vector<int> C(m + 1, -1);
	vector<int> X(S), Y(S);
	for (int i = 0; i < n; i++)
		g[order[i]].mode = A[i];
	for (int i = n; i + 1 < g.size(); i++) {
		if (g[i].l < n) X[g[i].ind - 1] = g[g[i].l].mode;
		else X[g[i].ind - 1] = -g[g[i].l].ind;

		if (g[i].r < n) Y[g[i].ind - 1] = g[g[i].r].mode;
		else if (g[i].r == md) Y[g[i].ind - 1] = 0;
		else Y[g[i].ind - 1] = -g[g[i].r].ind;
	}
	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void walk()':
doll.cpp:43:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |  while (order.size() < n) {
      |         ~~~~~~~~~~~~~^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:83:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for (int i = n; i + 1 < g.size(); i++) {
      |                  ~~~~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 63 ms 7292 KB Output is correct
3 Correct 76 ms 7028 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1356 KB Output is correct
6 Correct 99 ms 10208 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 63 ms 7292 KB Output is correct
3 Correct 76 ms 7028 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1356 KB Output is correct
6 Correct 99 ms 10208 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 160 ms 12336 KB Output is correct
9 Correct 138 ms 12788 KB Output is correct
10 Correct 260 ms 18760 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 63 ms 7292 KB Output is correct
3 Correct 76 ms 7028 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1356 KB Output is correct
6 Correct 99 ms 10208 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 160 ms 12336 KB Output is correct
9 Correct 138 ms 12788 KB Output is correct
10 Correct 260 ms 18760 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 202 ms 18168 KB Output is correct
15 Correct 140 ms 12188 KB Output is correct
16 Correct 237 ms 17820 KB Output is correct
17 Correct 2 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 196 ms 18308 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 122 ms 12172 KB Output is correct
3 Correct 138 ms 12184 KB Output is correct
4 Correct 183 ms 16588 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 122 ms 12172 KB Output is correct
3 Correct 138 ms 12184 KB Output is correct
4 Correct 183 ms 16588 KB Output is correct
5 Correct 200 ms 17676 KB Output is correct
6 Correct 206 ms 17356 KB Output is correct
7 Correct 190 ms 17400 KB Output is correct
8 Correct 194 ms 17152 KB Output is correct
9 Correct 123 ms 12188 KB Output is correct
10 Correct 227 ms 17144 KB Output is correct
11 Correct 211 ms 16904 KB Output is correct
12 Correct 137 ms 12212 KB Output is correct
13 Correct 145 ms 12220 KB Output is correct
14 Correct 122 ms 12188 KB Output is correct
15 Correct 120 ms 12184 KB Output is correct
16 Correct 4 ms 692 KB Output is correct
17 Correct 106 ms 11408 KB Output is correct
18 Correct 145 ms 12212 KB Output is correct
19 Correct 126 ms 12164 KB Output is correct
20 Correct 208 ms 16952 KB Output is correct
21 Correct 223 ms 16844 KB Output is correct
22 Correct 220 ms 16884 KB Output is correct