oj.uz

Submission #74978

# Submission time Handle Problem Language Result Execution time Memory
74978 2018-09-07T20:16:35 Z fahrbach Mechanical Doll (IOI18_doll) C++14
53 / 100
 501 ms 41488 KB 
#include "doll.h"

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

map<int, int> C, X, Y;
map<int, int> switch_for_node;
map<int, vi> leaves_for_nodes_switch;
map<int, ii> switch_adj;
int num_switches = 0;

vvi table;

void build_lookup_table() {
  table = vvi(20);
  // Base case
  table[1].push_back(1);
  table[1].push_back(2);
  for (int i = 2; i <= 18; i++) {
    table[i] = table[i - 1];
    for (int j = 0; j < table[i].size(); j++) {
      table[i][j] = 2*table[i][j] - 1;
    }
    int n = table[i].size();
    for (int j = 0; j < n; j++) {
      table[i].push_back(table[i][j] + 1);
    }
  }
  /*
  for (int i = 1; i <= 3; i++) {
    cout << i << endl;
    for (int j = 0; j < table[i].size(); j++) {
      cout << table[i][j] << " ";
    }
    cout << endl;
  }
  */
}

int offset(int i) {
  return -(num_switches + i);
}

// returns true root and true leaves
// builds all internal connections and points leaf exits to themselves via
// switch_adj
pair<int, vi> make_new_switch_hub(int deg) {
  int levels = 1;
  while ((1 << levels) < deg) levels++;
  //cout << " - levels: " << levels << endl;
  int num_nodes = (1 << levels) - 1;
  //cout << " - num_nodes: " << num_nodes << endl;
  
  // Build internal connections
  int root = offset(1);
  for (int i = 1; i < (1 << (levels-1)); i++) {
    //cout << " - " << i << endl;
    switch_adj[offset(i)].first = offset(2*i);
    switch_adj[offset(i)].second = offset(2*i + 1);
  }
  vi leaves;
  for (int i = (1 << (levels - 1)); i <= num_nodes; i++) {
    //cout << " - leaves: " << i << endl;
    leaves.push_back(offset(i));
    switch_adj[offset(i)].first = root;
    switch_adj[offset(i)].second = root;
  }
  num_switches += num_nodes;
  return make_pair(root, leaves);
}

void create_circuit(int M, std::vector<int> A) {
  build_lookup_table();
  int N = A.size();
  map<int, vii> out_edges;
  out_edges[0].push_back(ii(0, A[0]));
  for (int i = 1; i <= M; i++) out_edges[i] = vii();
  for (int i = 0; i < N - 1; i++) {
    //cout << i << ": " << A[i] << endl;
    int order = out_edges[A[i]].size();
    out_edges[A[i]].push_back(ii(order, A[i + 1]));
  }
  {
    int order = out_edges[A[N-1]].size();
    out_edges[A[N-1]].push_back(ii(order, 0));
  }
  /*
  for (auto kv : out_edges) {
    cout << kv.first << ": ";
    for (auto p : kv.second) cout << p.second << ", ";
    cout << endl;
  }
  */

  // Output
  for (int i = 0; i <= M; i++) {
    //cout << i << ": ";
    //for (auto p : out_edges[i]) cout << p.second << ", ";
    //cout << endl;
    
    int deg = out_edges[i].size();
    if (deg == 0) { // point to self
      //cout << " - self: " << i << endl;
      C[i] = i;
      continue;
    }
    if (deg == 1) { // point to next
      C[i] = out_edges[i][0].second;
      //cout << " - next: " << C[i] << endl;
      continue;
    }
    // Build switches
    //cout << " - deg: " << deg << endl;
    pair<int, vi> switch_hub = make_new_switch_hub(deg);
    C[i] = switch_hub.first;
    const vi& leaves = switch_hub.second;
    int num_leaves = leaves.size();
    //cout << " - num_leaves: " << num_leaves << endl;
    map<int, int> leaf_pointer;
    int offset2 = 2*num_leaves - out_edges[i].size() + 1;
    for (auto p : out_edges[i]) {
      leaf_pointer[p.first + offset2] = p.second;
    }
    int levels = 1;
    while ((1 << levels) < deg) levels++;
    for (int i = 0; i < num_leaves; i++) {
      //cout << " - " << i << ": " << leaves[i] << " -> ";
      //cout << table[levels][2*i] << " " << table[levels][2*i + 1] << endl;
      int left = table[levels][2*i];
      int right = table[levels][2*i + 1];
      if (leaf_pointer.count(left)) {
        int node = leaf_pointer[left];
        //cout << "  - left: " << node << endl;
        switch_adj[leaves[i]].first = node;
      }
      if (leaf_pointer.count(right)) {
        int node = leaf_pointer[right];
        //cout << "  - right: " << node << endl;
        switch_adj[leaves[i]].second = node;
      }
    }
  }

  //cout << "-------------------------------------" << endl;
  // Construct answer
  vi vector_C;
  for (int i = 0; i <= M; i++) {
    vector_C.push_back(C[i]);
    //cout << i << ": " << C[i] << endl;
  }
  vi vector_X, vector_Y;
  for (int i = -1; i >= -num_switches; i--) {
    //cout << i << ": " << switch_adj[i].first << " " << switch_adj[i].second << endl;
    vector_X.push_back(switch_adj[i].first);
    vector_Y.push_back(switch_adj[i].second);
  }
  //cout << "num switches: " << num_switches << endl;
  
  answer(vector_C, vector_X, vector_Y);
}

Compilation message

doll.cpp: In function 'void build_lookup_table()':
doll.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int j = 0; j < table[i].size(); j++) {
      |                     ~~^~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2400 KB Output is correct
2 Correct 161 ms 19000 KB Output is correct
3 Correct 135 ms 14152 KB Output is correct
4 Correct 6 ms 2468 KB Output is correct
5 Correct 84 ms 16648 KB Output is correct
6 Correct 229 ms 20168 KB Output is correct
7 Correct 4 ms 2372 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2400 KB Output is correct
2 Correct 161 ms 19000 KB Output is correct
3 Correct 135 ms 14152 KB Output is correct
4 Correct 6 ms 2468 KB Output is correct
5 Correct 84 ms 16648 KB Output is correct
6 Correct 229 ms 20168 KB Output is correct
7 Correct 4 ms 2372 KB Output is correct
8 Correct 263 ms 20992 KB Output is correct
9 Correct 327 ms 24484 KB Output is correct
10 Correct 470 ms 30732 KB Output is correct
11 Correct 4 ms 2372 KB Output is correct
12 Correct 4 ms 2372 KB Output is correct
13 Correct 5 ms 2556 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2400 KB Output is correct
2 Correct 161 ms 19000 KB Output is correct
3 Correct 135 ms 14152 KB Output is correct
4 Correct 6 ms 2468 KB Output is correct
5 Correct 84 ms 16648 KB Output is correct
6 Correct 229 ms 20168 KB Output is correct
7 Correct 4 ms 2372 KB Output is correct
8 Correct 263 ms 20992 KB Output is correct
9 Correct 327 ms 24484 KB Output is correct
10 Correct 470 ms 30732 KB Output is correct
11 Correct 4 ms 2372 KB Output is correct
12 Correct 4 ms 2372 KB Output is correct
13 Correct 5 ms 2556 KB Output is correct
14 Correct 494 ms 34056 KB Output is correct
15 Correct 274 ms 19220 KB Output is correct
16 Correct 373 ms 27052 KB Output is correct
17 Correct 4 ms 2372 KB Output is correct
18 Correct 4 ms 2500 KB Output is correct
19 Correct 4 ms 2500 KB Output is correct
20 Correct 485 ms 31544 KB Output is correct
21 Correct 5 ms 2472 KB Output is correct
22 Correct 4 ms 2372 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 2372 KB Output is partially correct
2 Correct 295 ms 19028 KB Output is correct
3 Partially correct 428 ms 29540 KB Output is partially correct
4 Partially correct 484 ms 32020 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 2372 KB Output is partially correct
2 Correct 295 ms 19028 KB Output is correct
3 Partially correct 428 ms 29540 KB Output is partially correct
4 Partially correct 484 ms 32020 KB Output is partially correct
5 Partially correct 446 ms 37436 KB Output is partially correct
6 Partially correct 423 ms 38972 KB Output is partially correct
7 Partially correct 418 ms 38128 KB Output is partially correct
8 Partially correct 379 ms 40512 KB Output is partially correct
9 Partially correct 331 ms 28264 KB Output is partially correct
10 Partially correct 501 ms 40372 KB Output is partially correct
11 Partially correct 408 ms 41488 KB Output is partially correct
12 Partially correct 268 ms 28100 KB Output is partially correct
13 Partially correct 248 ms 27144 KB Output is partially correct
14 Partially correct 257 ms 25840 KB Output is partially correct
15 Partially correct 264 ms 25016 KB Output is partially correct
16 Partially correct 9 ms 3012 KB Output is partially correct
17 Partially correct 273 ms 22980 KB Output is partially correct
18 Partially correct 235 ms 22516 KB Output is partially correct
19 Partially correct 239 ms 24084 KB Output is partially correct
20 Partially correct 352 ms 30392 KB Output is partially correct
21 Partially correct 379 ms 36324 KB Output is partially correct
22 Partially correct 310 ms 28652 KB Output is partially correct