oj.uz

Submission #82002

# Submission time Handle Problem Language Result Execution time Memory
82002 2018-10-28T11:11:58 Z lovemathboy Mechanical Doll (IOI18_doll) C++14
100 / 100
 149 ms 16072 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

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

int n, m;
vector<int> a, b;
vector<int> x, y;

void build(int p, int l, int r) {
	if (l == r-1) {
		if (b[l] <= n) {
			x[p-1] = a[b[l]];
		}
		else x[p-1] = -1;
		if (b[r] <= n) {
			y[p-1] = a[b[r]];
		}
		else y[p-1] = -1;
	}
	else {
		x[p-1] = -(2*p);
		y[p-1] = -(2*p+1);
		int mid = (l+r)/2;
		build(2*p, l, mid);
		build(2*p+1, mid+1, r);
		if (x[2*p-1] == -1 && y[2*p-1] == -1) {
			x[p-1] = -1;
			x[2*p-1] = 1012345678; //flag for it to be deleted
			y[2*p-1] = 1012345678; //flag for it to be deleted
		}
		if (x[2*p] == -1 && y[2*p] == -1) {
			y[p-1] = -1;
			x[2*p] = 1012345678; //flag for it to be deleted
			y[2*p] = 1012345678; //flag for it to be deleted
		}
	}
}

void create_circuit(int M, vector<int> A) {
	a = A; m = M;
	n = A.size();
	b.push_back(0);
	a.push_back(0);
	while (b.size() < n+1) {
		vector<int> temp;
		for (int i = 0; i < b.size(); i++) {
			temp.push_back(b[i]);
			temp.push_back(b[i] + b.size());
		}
		b = temp;
	}
	for (int i = 0; i < b.size() - a.size(); i++) {
		b[i] = 1012345678;
	}
	vector<int> temp = b;
	sort(temp.begin(), temp.end());
	vector<int> re;
	re.resize(temp.size()+1);
	for (int i = 0; i< temp.size(); i++) {
		if (temp[i] != 1012345678) {
			re[temp[i]] = i;
		}
		else break;
	}
	for (int i = 0; i < b.size(); i++) {
		if (b[i] != 1012345678) b[i] = re[b[i]];
	}
	/*for (int i = 0; i < b.size(); i++) {
		printf("%d ", b[i]);
	}
	printf("\n");
	for (int i = 0; i < a.size(); i++) {
		printf("%d ", a[i]);
	}
	printf("\n");*/
	vector<int> C(M + 1);
	for (int i = 0; i <= m; i++) {
		C[i] = -1;
	}
	x.resize(b.size()-1); y.resize(b.size()-1);
	build(1, 0, b.size()-1);
	re.clear();
	re.resize(b.size());
	int cnt = -1;
	for (int i = 0; i < x.size(); i++) {
		if (x[i] != 1012345678) {
			re[i] = cnt;
			cnt--;
		}
	}
	vector<int> X, Y;
	for (int i = 0; i < x.size(); i++) {
		if (x[i] == 1012345678) continue;
		if (x[i] < 0) X.push_back(re[-x[i]-1]);
		else X.push_back(x[i]);
		if (y[i] < 0) Y.push_back(re[-y[i]-1]);
		else Y.push_back(y[i]);
	}
	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:46:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |  while (b.size() < n+1) {
      |         ~~~~~~~~~^~~~~
doll.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int i = 0; i < b.size(); i++) {
      |                   ~~^~~~~~~~~~
doll.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for (int i = 0; i < b.size() - a.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~
doll.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 0; i< temp.size(); i++) {
      |                  ~^~~~~~~~~~~~~
doll.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (int i = 0; i < b.size(); i++) {
      |                  ~~^~~~~~~~~~
doll.cpp:87:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for (int i = 0; i < x.size(); i++) {
      |                  ~~^~~~~~~~~~
doll.cpp:94:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for (int i = 0; i < x.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 51 ms 7516 KB Output is correct
3 Correct 41 ms 6944 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1356 KB Output is correct
6 Correct 59 ms 9152 KB Output is correct
7 Correct 2 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 51 ms 7516 KB Output is correct
3 Correct 41 ms 6944 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1356 KB Output is correct
6 Correct 59 ms 9152 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 87 ms 13112 KB Output is correct
9 Correct 110 ms 13080 KB Output is correct
10 Correct 123 ms 16072 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 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 51 ms 7516 KB Output is correct
3 Correct 41 ms 6944 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1356 KB Output is correct
6 Correct 59 ms 9152 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 87 ms 13112 KB Output is correct
9 Correct 110 ms 13080 KB Output is correct
10 Correct 123 ms 16072 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 112 ms 15876 KB Output is correct
15 Correct 94 ms 12856 KB Output is correct
16 Correct 149 ms 15768 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 264 KB Output is correct
20 Correct 117 ms 15960 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 2 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 2 ms 204 KB Output is correct
8 Correct 2 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 71 ms 11420 KB Output is correct
3 Correct 68 ms 11404 KB Output is correct
4 Correct 116 ms 14480 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 71 ms 11420 KB Output is correct
3 Correct 68 ms 11404 KB Output is correct
4 Correct 116 ms 14480 KB Output is correct
5 Correct 108 ms 15632 KB Output is correct
6 Correct 144 ms 15316 KB Output is correct
7 Correct 114 ms 15304 KB Output is correct
8 Correct 130 ms 15248 KB Output is correct
9 Correct 97 ms 11424 KB Output is correct
10 Correct 103 ms 15116 KB Output is correct
11 Correct 103 ms 14880 KB Output is correct
12 Correct 67 ms 11704 KB Output is correct
13 Correct 76 ms 11888 KB Output is correct
14 Correct 73 ms 11932 KB Output is correct
15 Correct 68 ms 11940 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 63 ms 8732 KB Output is correct
18 Correct 71 ms 11692 KB Output is correct
19 Correct 93 ms 11708 KB Output is correct
20 Correct 119 ms 15080 KB Output is correct
21 Correct 109 ms 14844 KB Output is correct
22 Correct 110 ms 14884 KB Output is correct