Submission #130128

#	Time	Username	Problem	Language	Result	Execution time	Memory
130128		cjoa	Mechanical Doll (IOI18_doll)	C++11	85.55 / 100	203 ms	17240 KiB

doll

#include "doll.h"

#include <vector>
#include <cassert>
#include <cstdio>

using namespace std;


namespace TreeSol {

typedef vector<int> VI;

struct Node {
   int L, R;
   int id;
   bool flipped, loop;
   Node(int _L = -1, int _R = -1, int _id = 999999)
      : L(_L), R(_R), id(_id), flipped(false), loop(false) {}
};

vector<Node> nodes;

int g_num_switches = 0;
void build_tree(int p, int q, int idx, int L, int R) {
   if (p > R || q < L) {
      nodes[idx] = Node(L, R, nodes[1].id);  // root
      nodes[idx].loop = true;
      return;
   }
   if (L == R) {
      nodes[idx] = Node(L, R);
      return;
   }
   int mid = (L+R)/2;
   g_num_switches++;
   nodes[idx] = Node(L, R, -g_num_switches);
   build_tree(p, q, idx*2, L, mid);
   build_tree(p, q, idx*2+1, mid+1, R);
}

void assign_device_id(int id, int idx = 1) {
   if (nodes[idx].loop) {
      assign_device_id(id, 1);
      return;
   }
   if (nodes[idx].L == nodes[idx].R) {
      nodes[idx].id = id;
      return;
   }
   nodes[idx].flipped = !nodes[idx].flipped;
   if (nodes[idx].flipped)
      assign_device_id(id, 2*idx);
   else
      assign_device_id(id, 2*idx+1);
}

struct Switch {
   int x, y;
};
vector<Switch> switches;


void assign_switch_exits(int idx = 1) {
   if (nodes[idx].L < 0) return;
   if (nodes[idx].loop) return;
   if (nodes[idx].L == nodes[idx].R) return;
   assign_switch_exits(idx*2);
   assign_switch_exits(idx*2 + 1);
   assert(nodes[idx].id < 0);
   int switch_id = -(nodes[idx].id+1);
   switches[ switch_id ].x = nodes[idx*2  ].id;
   switches[ switch_id ].y = nodes[idx*2+1].id;
}

int build_circuit(int src, const VI& nxt) {
   int K = nxt.size();
   if (K == 1)
      return nxt[0];

   int nodes_last_level = 1;
   while (nodes_last_level < K)
      nodes_last_level *= 2;

   nodes = vector<Node>(2*nodes_last_level + 1);

   /*
   if (src == 3) {
      fprintf(stderr, "nodes_last_level: %d\n", nodes_last_level);
      fprintf(stderr, "p: %d  q: %d\n", nodes_last_level-K, nodes_last_level-1);
   }
   */

   build_tree(nodes_last_level - K, nodes_last_level - 1,
              1, 0, nodes_last_level-1);

   int ret = nodes[1].id;

   for (int dev_id : nxt)
      assign_device_id(dev_id);

   /*
   if (src == 3) {
      for (int idx = 1; idx < int(nodes.size()); ++idx) {
         Node x = nodes[idx];
         fprintf(stderr, "idx:%d  L:%d  R:%d  id:%d  loop:%d\n",
                 idx, x.L, x.R, x.id, x.loop);
      }
   }
   */

   switches.resize(g_num_switches);
   assign_switch_exits();

   return ret;
}

}

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

   vector< vector<int> > nxt(M+1);
   for (int i = 1; i < N; ++i)
      nxt[ A[i-1] ].push_back( A[i] );
   nxt[ A.back() ].push_back(0);

   vector<int> C(M + 1);
   C[0] = A[0];

   for (int i = 1; i <= M; ++i) {
      if (nxt[i].empty()) continue;
      C[i] = TreeSol::build_circuit(i, nxt[i]);
   }

   int S = TreeSol::switches.size();
   vector<int> X(S), Y(S);
   for (int j = 0; j < S; ++j) {
      X[j] = TreeSol::switches[j].x;
      Y[j] = TreeSol::switches[j].y;
   }

   answer(C, X, Y);
}

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