oj.uz

Submission #172243

# Submission time Handle Problem Language Result Execution time Memory
172243 2019-12-31T19:21:34 Z AlexLuchianov Mechanical Doll (IOI18_doll) C++14
100 / 100
 127 ms 11624 KB 
#include "doll.h"
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

#define ll long long

int const nmax = 800000;
std::vector<int> v;
std::vector<int> soltriggers;
std::vector<int> sol;

int rev(int n, int number){
  int p = 0;
  while((1 << p) < n)
    p++;
  int result = 0;
  for(int i = 0; i < p; i++)
    if(0 < (number & (1 << i)))
      result |= (1 << (p - 1 - i));
  return result;
}

std::vector<int> left, right;
int devices = 0;

int isempty[1 + nmax];

void precompute(int node, int from, int to){
  if(from < to){
    int mid = (from + to) / 2;
    precompute(node * 2, from, mid);
    precompute(node * 2 + 1, mid + 1, to);
    isempty[node] = isempty[node * 2] | isempty[node * 2 + 1];
  } else
    isempty[node] = (0 <= v[from]);
}

int build(int node, int from, int to){
  if(isempty[node] == 0)
    return -1;
  else if(from < to){
    ++devices;
    int id = devices;
    left.push_back(0);
    right.push_back(0);
    int mid = (from + to) / 2;
    int lft = build(node * 2, from, mid);
    int rght = build(node * 2 + 1, mid + 1, to);
    left[id - 1] = lft;
    right[id - 1] = rght;
    return -id;
  } else
    return v[from];
}
void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  std::vector<int> initv;
  for(int i = 0; i < N; i++)
    initv.push_back(A[i]);
  initv.push_back(0);
  soltriggers.resize(1 + M);

  int n = 1;
  while(n < initv.size())
    n *= 2;
  int unused = n - initv.size();
  v.resize(n);
  int ptr = 0;
  for(int i = 0; i < n; i++)
    v[i] = -1;
  for(int i = 0; i < n; i++) {
    int pos = rev(n, i);
    if(unused <= pos)
      v[pos] = initv[ptr++];
  }
  for(int i = 0;i <= M; i++)
    soltriggers[i] = -1;
  precompute(1, 0, n - 1);
  soltriggers[0] = build(1, 0, n - 1);

  answer(soltriggers, left, right);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:66:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   while(n < initv.size())
      |         ~~^~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 47 ms 5816 KB Output is correct
3 Correct 43 ms 5664 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1484 KB Output is correct
6 Correct 60 ms 6684 KB Output is correct
7 Correct 1 ms 256 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 47 ms 5816 KB Output is correct
3 Correct 43 ms 5664 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1484 KB Output is correct
6 Correct 60 ms 6684 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 83 ms 9548 KB Output is correct
9 Correct 82 ms 10088 KB Output is correct
10 Correct 110 ms 11624 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 47 ms 5816 KB Output is correct
3 Correct 43 ms 5664 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1484 KB Output is correct
6 Correct 60 ms 6684 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 83 ms 9548 KB Output is correct
9 Correct 82 ms 10088 KB Output is correct
10 Correct 110 ms 11624 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 110 ms 11112 KB Output is correct
15 Correct 79 ms 9052 KB Output is correct
16 Correct 104 ms 10980 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 304 KB Output is correct
20 Correct 105 ms 11340 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 79 ms 8176 KB Output is correct
3 Correct 74 ms 8140 KB Output is correct
4 Correct 95 ms 10520 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 79 ms 8176 KB Output is correct
3 Correct 74 ms 8140 KB Output is correct
4 Correct 95 ms 10520 KB Output is correct
5 Correct 104 ms 10956 KB Output is correct
6 Correct 100 ms 10592 KB Output is correct
7 Correct 112 ms 10720 KB Output is correct
8 Correct 99 ms 10596 KB Output is correct
9 Correct 75 ms 8156 KB Output is correct
10 Correct 96 ms 10592 KB Output is correct
11 Correct 98 ms 10464 KB Output is correct
12 Correct 83 ms 8388 KB Output is correct
13 Correct 77 ms 8800 KB Output is correct
14 Correct 81 ms 8836 KB Output is correct
15 Correct 77 ms 9008 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 84 ms 6824 KB Output is correct
18 Correct 91 ms 8296 KB Output is correct
19 Correct 78 ms 8384 KB Output is correct
20 Correct 99 ms 10508 KB Output is correct
21 Correct 127 ms 10468 KB Output is correct
22 Correct 127 ms 10504 KB Output is correct