oj.uz

Submission #77190

# Submission time Handle Problem Language Result Execution time Memory
77190 2018-09-23T17:43:11 Z kimjihoon Mechanical Doll (IOI18_doll) C++14
100 / 100
 179 ms 20816 KB 
#include "doll.h"
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

vector<int> r[100009], st, c, x, y, rx, ry;
vector<pair<int, pair<int, int> > > sq;
int sc = 0, rc = -1, ft;

int vsq(int n, int ts, int te, int t)
{
	if (ts >= te)
		return 0;
	int md = (ts + te) / 2;
	if (n <= md)
		return vsq(n, ts, md, t * 2);
	else
		return vsq(n, md + 1, te, t * 2) + t;
}

int vsq(int n, int tn) 
{
	return vsq(n, 0, tn - 1, 1);
}

int csw(int n, int tn)
{
	sc--;
	int tsc = sc;
	if (ft >= n / 2) {
		ft -= n / 2;
		x[-sc - 1] = -1;
		rc += n / 2;
		if (ft >= n / 2) {
			ft -= n / 2;
			y[-sc - 1] = -1;
			rc += n / 2;
		}
		else {
			if (n == 2) {
				rc++;
				sq.push_back(make_pair(vsq(rc, tn), make_pair(-sc - 1, 1)));
			}
			else 
				y[-tsc - 1] = csw(n / 2, tn);
		}
		return tsc;
	}
	if (n == 2) {
		rc++;
		sq.push_back(make_pair(vsq(rc, tn), make_pair(-sc - 1, 0)));
		rc++;
		sq.push_back(make_pair(vsq(rc, tn), make_pair(-sc - 1, 1)));
		return sc;
	}
	int a = csw(n / 2, tn), b = csw(n / 2, tn);
	x[-tsc - 1] = a; y[-tsc - 1] = b;
	return tsc;
}

void create_circuit(int M, std::vector<int> A) {
	A.push_back(0);
	int N = A.size();
	for (int i = 0; i < N - 1; i++)
		r[A[i]].push_back(A[i + 1]);
	for (int i = 0; i < N - 1; i++)
		if (r[A[i]].size() > 1)
			st.push_back(A[i + 1]);
	int t = 1, rn = 0;
	while (t < st.size()) {
		rn += t; t *= 2;
	}
	int rp = t - st.size();
	for (int i = 0; i < rn; i++) {
		x.push_back(100009);
		y.push_back(100009);
	}
	ft = rp;
	if (N > 2 && st.size() > 0) {
		csw(t, t);
		sort(sq.begin(), sq.end());
		for (int i = 0; i < sq.size(); i++) {
			if (sq[i].second.second == 0)
				x[sq[i].second.first] = st[i];
			else
				y[sq[i].second.first] = st[i];
		}	
	}
	c.push_back(A[0]);
	for (int i = 1; i <= M; i++) {
		if (r[i].size() == 0)
			c.push_back(0);
		else if (r[i].size() == 1)
			c.push_back(r[i][0]);
		else
			c.push_back(-1);
	}
	for (int i = 0; i < x.size() && x[i] != 100009; i++)
		rx.push_back(x[i]);
	for (int i = 0; i < y.size() && y[i] != 100009; i++)
		ry.push_back(y[i]);
	answer(c, rx, ry);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:72:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  while (t < st.size()) {
      |         ~~^~~~~~~~~~~
doll.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int i = 0; i < sq.size(); i++) {
      |                   ~~^~~~~~~~~~~
doll.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (int i = 0; i < x.size() && x[i] != 100009; i++)
      |                  ~~^~~~~~~~~~
doll.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for (int i = 0; i < y.size() && y[i] != 100009; i++)
      |                  ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 51 ms 6468 KB Output is correct
3 Correct 34 ms 6028 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 16 ms 3908 KB Output is correct
6 Correct 41 ms 7884 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 51 ms 6468 KB Output is correct
3 Correct 34 ms 6028 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 16 ms 3908 KB Output is correct
6 Correct 41 ms 7884 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 95 ms 14648 KB Output is correct
9 Correct 85 ms 13436 KB Output is correct
10 Correct 148 ms 20816 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 3 ms 2636 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 51 ms 6468 KB Output is correct
3 Correct 34 ms 6028 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 16 ms 3908 KB Output is correct
6 Correct 41 ms 7884 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 95 ms 14648 KB Output is correct
9 Correct 85 ms 13436 KB Output is correct
10 Correct 148 ms 20816 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 3 ms 2636 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct
14 Correct 147 ms 19520 KB Output is correct
15 Correct 92 ms 14000 KB Output is correct
16 Correct 142 ms 18876 KB Output is correct
17 Correct 3 ms 2636 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 3 ms 2636 KB Output is correct
20 Correct 179 ms 19400 KB Output is correct
21 Correct 3 ms 2636 KB Output is correct
22 Correct 3 ms 2636 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 70 ms 11704 KB Output is correct
3 Correct 72 ms 12508 KB Output is correct
4 Correct 114 ms 16156 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 70 ms 11704 KB Output is correct
3 Correct 72 ms 12508 KB Output is correct
4 Correct 114 ms 16156 KB Output is correct
5 Correct 144 ms 19392 KB Output is correct
6 Correct 135 ms 18336 KB Output is correct
7 Correct 140 ms 18404 KB Output is correct
8 Correct 149 ms 18064 KB Output is correct
9 Correct 76 ms 12772 KB Output is correct
10 Correct 119 ms 18308 KB Output is correct
11 Correct 116 ms 17636 KB Output is correct
12 Correct 75 ms 13484 KB Output is correct
13 Correct 84 ms 13108 KB Output is correct
14 Correct 99 ms 14008 KB Output is correct
15 Correct 89 ms 14180 KB Output is correct
16 Correct 5 ms 3020 KB Output is correct
17 Correct 78 ms 12496 KB Output is correct
18 Correct 73 ms 12352 KB Output is correct
19 Correct 82 ms 13260 KB Output is correct
20 Correct 123 ms 17348 KB Output is correct
21 Correct 150 ms 17228 KB Output is correct
22 Correct 119 ms 16960 KB Output is correct