oj.uz

Submission #296156

# Submission time Handle Problem Language Result Execution time Memory
296156 2020-09-10T10:58:40 Z Bruteforceman Mechanical Doll (IOI18_doll) C++11
100 / 100
 181 ms 27672 KB 
#include "bits/stdc++.h"
#include "doll.h"
using namespace std;
const int maxn = 5e5 + 10;
vector <int> g[maxn];
int l[maxn], r[maxn];
bool leaf[maxn];
int to[maxn];
int node = 0;

int create(int b, int e, vector <int> &order) {
  int cur = ++node;
  if(b == e) {
    leaf[cur] = true;
    order.push_back(cur);
    order.push_back(cur);
    return cur; 
  }
  int mid = (b + e) >> 1;
  vector <int> left, right;
  l[cur] = create(b, mid, left);
  r[cur] = create(mid + 1, e, right);
  for(int i = 0; i < left.size(); i++) {
    order.push_back(left[i]);
    order.push_back(right[i]);
  }
  return cur;
}

void getEdges(int M, vector <int> arr) {
  int sz = arr.size();
  int bit = __lg(sz) + 1;
  node = bit;
  vector <int> order;
  leaf[1] = true;
  order.push_back(1);
  order.push_back(1);
  for(int i = 1; i < bit; i++) {
    int cur = i + 1;
    r[cur] = i;
    vector <int> v;
    if((sz >> i) & 1) {
      l[cur] = create(1, 1 << (i - 1), v);
    } else {
      l[cur] = bit;
      v.resize(1 << i);
    }
    vector <int> aux;
    for(int i = 0; i < v.size(); i++) {
      aux.push_back(v[i]);
      aux.push_back(order[i]);
    }
    order = aux;
  }
  set <int> cont;
  int pt = 0;
  for(int i = 0; i < order.size(); i++) {
    if(order[i] == 0) continue;
    if(cont.count(order[i])) {
      if(pt < arr.size()) {
        r[order[i]] = arr[pt++]; 
      } else {
        r[order[i]] = -bit;
      }
    } else {
      if(pt < arr.size()) {
        l[order[i]] = arr[pt++];
      } else {
        l[order[i]] = -bit;
      }
    }
    cont.insert(order[i]);
  }
  r[1] = 0; 
  for(int i = 0; i <= M; i++) to[i] = -bit;
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  getEdges(M, A);
  vector <int> C(M + 1);
  vector <int> X (node), Y (node);
  for(int i = 0; i <= M; i++) {
    C[i] = to[i];
  }
  for(int i = 1; i <= node; i++) {
    if(leaf[i]) {
      X[i - 1] = l[i];
      Y[i - 1] = r[i];
    } else {
      X[i - 1] = -l[i];
      Y[i - 1] = -r[i];
    }
  }
  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'int create(int, int, std::vector<int>&)':
doll.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for(int i = 0; i < left.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
doll.cpp: In function 'void getEdges(int, std::vector<int>)':
doll.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i = 0; i < v.size(); i++) {
      |                    ~~^~~~~~~~~~
doll.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int i = 0; i < order.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
doll.cpp:60:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |       if(pt < arr.size()) {
      |          ~~~^~~~~~~~~~~~
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 |       if(pt < arr.size()) {
      |          ~~~^~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:79:7: warning: unused variable 'N' [-Wunused-variable]
   79 |   int N = A.size();
      |       ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12068 KB Output is correct
2 Correct 70 ms 18932 KB Output is correct
3 Correct 67 ms 18144 KB Output is correct
4 Correct 10 ms 11980 KB Output is correct
5 Correct 19 ms 13516 KB Output is correct
6 Correct 115 ms 21324 KB Output is correct
7 Correct 9 ms 11980 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12068 KB Output is correct
2 Correct 70 ms 18932 KB Output is correct
3 Correct 67 ms 18144 KB Output is correct
4 Correct 10 ms 11980 KB Output is correct
5 Correct 19 ms 13516 KB Output is correct
6 Correct 115 ms 21324 KB Output is correct
7 Correct 9 ms 11980 KB Output is correct
8 Correct 133 ms 22176 KB Output is correct
9 Correct 132 ms 23604 KB Output is correct
10 Correct 166 ms 27672 KB Output is correct
11 Correct 9 ms 11980 KB Output is correct
12 Correct 10 ms 12032 KB Output is correct
13 Correct 10 ms 11980 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12068 KB Output is correct
2 Correct 70 ms 18932 KB Output is correct
3 Correct 67 ms 18144 KB Output is correct
4 Correct 10 ms 11980 KB Output is correct
5 Correct 19 ms 13516 KB Output is correct
6 Correct 115 ms 21324 KB Output is correct
7 Correct 9 ms 11980 KB Output is correct
8 Correct 133 ms 22176 KB Output is correct
9 Correct 132 ms 23604 KB Output is correct
10 Correct 166 ms 27672 KB Output is correct
11 Correct 9 ms 11980 KB Output is correct
12 Correct 10 ms 12032 KB Output is correct
13 Correct 10 ms 11980 KB Output is correct
14 Correct 150 ms 27432 KB Output is correct
15 Correct 135 ms 21800 KB Output is correct
16 Correct 170 ms 27212 KB Output is correct
17 Correct 12 ms 12008 KB Output is correct
18 Correct 11 ms 12064 KB Output is correct
19 Correct 8 ms 11968 KB Output is correct
20 Correct 151 ms 27488 KB Output is correct
21 Correct 9 ms 11980 KB Output is correct
22 Correct 9 ms 12044 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11952 KB Output is correct
2 Correct 8 ms 11972 KB Output is correct
3 Correct 10 ms 11980 KB Output is correct
4 Correct 8 ms 11980 KB Output is correct
5 Correct 8 ms 11980 KB Output is correct
6 Correct 10 ms 12052 KB Output is correct
7 Correct 8 ms 11980 KB Output is correct
8 Correct 9 ms 12036 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11980 KB Output is correct
2 Correct 99 ms 20544 KB Output is correct
3 Correct 113 ms 21024 KB Output is correct
4 Correct 142 ms 26200 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11980 KB Output is correct
2 Correct 99 ms 20544 KB Output is correct
3 Correct 113 ms 21024 KB Output is correct
4 Correct 142 ms 26200 KB Output is correct
5 Correct 149 ms 27336 KB Output is correct
6 Correct 159 ms 27096 KB Output is correct
7 Correct 153 ms 27472 KB Output is correct
8 Correct 147 ms 27168 KB Output is correct
9 Correct 98 ms 21296 KB Output is correct
10 Correct 179 ms 27140 KB Output is correct
11 Correct 175 ms 26636 KB Output is correct
12 Correct 101 ms 21232 KB Output is correct
13 Correct 133 ms 21872 KB Output is correct
14 Correct 102 ms 21960 KB Output is correct
15 Correct 133 ms 22172 KB Output is correct
16 Correct 12 ms 12304 KB Output is correct
17 Correct 113 ms 21744 KB Output is correct
18 Correct 117 ms 21600 KB Output is correct
19 Correct 98 ms 21668 KB Output is correct
20 Correct 173 ms 27064 KB Output is correct
21 Correct 181 ms 26780 KB Output is correct
22 Correct 172 ms 26860 KB Output is correct