oj.uz

Submission #129339

# Submission time Handle Problem Language Result Execution time Memory
129339 2019-07-12T04:08:42 Z Just_Solve_The_Problem Mechanical Doll (IOI18_doll) C++11
100 / 100
 265 ms 20632 KB 
#include <bits/stdc++.h>
#include "doll.h"
//#include "grader.cpp"

using namespace std;

const int maxn = (int)1e6 + 7;
const int inf = (int)1e6 + 6;

int sz;

void solve5(int M, vector<int> A) {
	int N = A.size();
  vector<int> C(M + 1);
  vector<int> X, Y;
	C[0] = A[0];
  int tmp = N - 1;
  while (tmp > 0) {
		sz++;
		tmp >>= 1;
  }
  if (sz) C[1] = -1;
  else C[1] = 0;
  X.resize(sz);
  Y.resize(sz);
  tmp = N - 1;
  for (int i = 1; i <= sz; i++) {
		if ((tmp >> (sz - i)) & 1) {
			X[i - 1] = A[0];
		} else {
			X[i - 1] = -1;
		}
		Y[i - 1] = ((i == sz) ? 0 : -(i + 1));
  }
  answer(C, X, Y);
}

vector <int> X, Y, a;
int ind = -1, siz;
int lim, NN;

int make(int l, int r) {
	if (r + NN < lim) return -1;
	if (l == r) {
    int cur = 0;
    for (int i = 0; i < siz; i++) {
      if ((l >> i) & 1) cur |= (1 << siz - i - 1);
    }
		return cur;
	}
	int mid = (l + r) >> 1;
	int a, b;
	int cur = ind--;
	a = make(l, mid);
	b = make(mid + 1, r);
	X[-cur - 1] = a;
	Y[-cur - 1] = b;
	return cur--;
}

void solve1234(int M, vector<int> _A) {
	a = _A;
	a.push_back(0);
	NN = a.size();
	lim = 1;
	while (lim < a.size()) {
    lim *= 2;
    siz++;
  }
  X.resize(lim);
	Y.resize(lim);
	vector <int> C(M + 1);
	if (NN == 1) {
		answer(C, X, Y);
		return ;
	}
	int qwe = make(0, lim - 1);
	fill(C.begin(), C.end(), qwe);
	while (X.back() == 0 && Y.back() == 0) {
		X.pop_back();
		Y.pop_back();
	}
	map<int, int> mp;
  for (int i = 0; i < X.size(); i++) {
		if (X[i] >= 0) mp[X[i]] = 0;
    if (Y[i] >= 0) mp[Y[i]] = 0;
	}
  int cnt = 0;
  for (auto &to : mp) {
    to.second = cnt++;
  }
  for (int i = 0; i < X.size(); i++) {
    if (X[i] >= 0) {
      X[i] = a[mp[X[i]]];
    }
    if (Y[i] >= 0) {
      Y[i] = a[mp[Y[i]]];
    }
  }
  //for (int i = 0; i < C.size(); i++) {
    //cout << C[i] << ' ';
  //}
  //cout << endl;
  //for (int i = 0; i < X.size(); i++) {
    //cout << X[i] << ' ' << Y[i] << endl;
  //}
	answer(C, X, Y);
}

void create_circuit(int M, vector<int> A) {
  if (M == 1) {
		solve5(M, A);
	} else {
		solve1234(M, A);
	}
}
/*
3 20
1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 3 3 3 3
4 2
1 2
3 5
1 2 1 2 2
*/

Compilation message

doll.cpp: In function 'int make(int, int)':
doll.cpp:47:46: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   47 |       if ((l >> i) & 1) cur |= (1 << siz - i - 1);
      |                                      ~~~~~~~~^~~
doll.cpp: In function 'void solve1234(int, std::vector<int>)':
doll.cpp:66:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  while (lim < a.size()) {
      |         ~~~~^~~~~~~~~~
doll.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int i = 0; i < X.size(); i++) {
      |                   ~~^~~~~~~~~~
doll.cpp:92:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   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 60 ms 7632 KB Output is correct
3 Correct 72 ms 7732 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1356 KB Output is correct
6 Correct 107 ms 11080 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 60 ms 7632 KB Output is correct
3 Correct 72 ms 7732 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1356 KB Output is correct
6 Correct 107 ms 11080 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 155 ms 14224 KB Output is correct
9 Correct 122 ms 14664 KB Output is correct
10 Correct 212 ms 20632 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 60 ms 7632 KB Output is correct
3 Correct 72 ms 7732 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1356 KB Output is correct
6 Correct 107 ms 11080 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 155 ms 14224 KB Output is correct
9 Correct 122 ms 14664 KB Output is correct
10 Correct 212 ms 20632 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 235 ms 19980 KB Output is correct
15 Correct 171 ms 13716 KB Output is correct
16 Correct 247 ms 19720 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 2 ms 204 KB Output is correct
20 Correct 220 ms 20168 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 27 ms 1740 KB Output is correct
3 Correct 17 ms 1732 KB Output is correct
4 Correct 27 ms 2616 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 27 ms 1740 KB Output is correct
3 Correct 17 ms 1732 KB Output is correct
4 Correct 27 ms 2616 KB Output is correct
5 Correct 209 ms 19652 KB Output is correct
6 Correct 208 ms 19328 KB Output is correct
7 Correct 208 ms 19480 KB Output is correct
8 Correct 254 ms 19048 KB Output is correct
9 Correct 133 ms 12688 KB Output is correct
10 Correct 215 ms 18936 KB Output is correct
11 Correct 265 ms 18608 KB Output is correct
12 Correct 140 ms 13000 KB Output is correct
13 Correct 116 ms 13336 KB Output is correct
14 Correct 115 ms 13476 KB Output is correct
15 Correct 156 ms 13640 KB Output is correct
16 Correct 5 ms 736 KB Output is correct
17 Correct 126 ms 12040 KB Output is correct
18 Correct 145 ms 12988 KB Output is correct
19 Correct 115 ms 13000 KB Output is correct
20 Correct 211 ms 18828 KB Output is correct
21 Correct 206 ms 18612 KB Output is correct
22 Correct 246 ms 18640 KB Output is correct