Submission #414445

#	Time	Username	Problem	Language	Result	Execution time	Memory
414445		DBPhoenix	Mechanical Doll (IOI18_doll)	C++17	6 / 100	141 ms	29508 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

struct Tree {
  int pointer = 1;
  vector<int> nodes = {0};
};

int switches = 0;
Tree tree[200001];

void insert(int i, int value)
{
  if (tree[i].pointer == 1) {
    tree[i].nodes.push_back(value);
    tree[i].pointer++;
    return;
  }

  int n = 2;
  while (n < tree[i].pointer) n *= 2;

  if (tree[i].pointer == n) {
    for (int j = 0; j < n; j++)
    {
      int _n = n + j;
      int common = n + j + 1;
      while (_n != common) {
        _n /= 2;
        common /= 2;
      }

      tree[i].nodes.push_back(tree[i].nodes[common]);
    }

    for (int j = 0; j < n; j += 2)
      tree[i].nodes[(tree[i].pointer + j) / 2] = -(++switches);

    tree[i].pointer++;
  }
  
  tree[i].nodes[tree[i].pointer] = value;
  
  if (tree[i].pointer == n * 2 - 1) tree[i].pointer++;
  else tree[i].pointer += 2;
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();

  int prev = 0;
  for (int a : A)
  {
    insert(prev, a);

    /*cout << "INSERT AT (" << prev << ") NODE: " << a << endl;
    for (int i = 0; i <= M; ++i)
    {
      for (int node : tree[i].nodes)
        cout << node << " ";
      cout << endl;
    }*/
    
    prev = a;
  }
  insert(prev, 0);

  /*for (int i = 0; i <= M; i++)
  {
    cout << "TREE " << i << ":" << endl;
    cout << "POINTER: " << tree[i].pointer << endl;
    for (int node : tree[i].nodes)
      cout << node << " ";
    cout << endl;
  }*/

  for (int i = 0; i <= M; i++)
  {
    int n = 2;
    while (n < tree[i].pointer) n *= 2;

    if (tree[i].pointer == n) continue;

    int value = tree[i].nodes[tree[i].pointer - 2];
    tree[i].nodes[n - 1] = value;
    
    int _pointer = tree[i].pointer - 2;
    int common = _pointer + 1;

    while (_pointer != common) {
      _pointer /= 2;
      common /= 2;
    }

    tree[i].nodes[tree[i].pointer - 2] = tree[i].nodes[common];
  }

  /*for (int i = 0; i <= M; i++)
  {
    cout << "TREE " << i << ":" << endl;

    for (int node : tree[i].nodes)
      cout << node << " ";
    cout << endl;
  }*/

  vector<int> C(M + 1);
  for (int i = 0; i <= M; ++i)
  {
    if (tree[i].nodes.size() < 2)
      C[i] = 1;
    else
      C[i] = tree[i].nodes[1];
  }

  vector<int> X(switches);
  vector<int> Y(switches);
  for (int i = 0; i <= M; i++)
  {
    for (int j = 1; true; j++)
      if (tree[i].nodes[j] > -1) break;
      else
      {
        X[-tree[i].nodes[j] - 1] = tree[i].nodes[j * 2];
        Y[-tree[i].nodes[j] - 1] = tree[i].nodes[j * 2 + 1];
      }
  }

  /*cout << "C: ";
  for (int c : C)
    cout << c << " ";
  cout << endl;

  cout << "X: ";
  for (int x : X)
    cout << x << " ";
  cout << endl;

  cout << "Y: ";
  for (int y : Y)
    cout << y << " ";
  cout << endl;*/

  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:51:7: warning: unused variable 'N' [-Wunused-variable]
   51 |   int N = A.size();
      |       ^

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56