Submission #74978

#	Time	Username	Problem	Language	Result	Execution time	Memory
74978		fahrbach	Mechanical Doll (IOI18_doll)	C++14	53 / 100	501 ms	41488 KiB

doll

#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 (stderr)

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56