Submission #130362

#	Time	Username	Problem	Language	Result	Execution time	Memory
130362		cjoa	Mechanical Doll (IOI18_doll)	C++11	85.55 / 100	244 ms	14580 KiB

doll

#include "doll.h"
 
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>
#include <cstdio>
 
using namespace std;
 
 
namespace TreeSol {
 
typedef vector<int> VI;
 
const int UNDEFINED = 999999;

struct Node {
   int L, R;
   int id;
   bool flipped, leaf;
   Node(int _L = -1, int _R = -1, int _id = UNDEFINED)
      : L(_L), R(_R), id(_id), flipped(false), leaf(false) {}
};
 
vector<Node> nodes;

void build_tree(int idx, int L, int R) {
   if (L == R) {
      nodes[idx] = Node(L, R);
      nodes[idx].leaf = true;
      return;
   }
   int mid = (L+R)/2;
   nodes[idx] = Node(L, R, -idx);
   build_tree(idx*2, L, mid);
   build_tree(idx*2+1, mid+1, R);
}
 
void assign_device_id(int id, int from, int idx = 1) {
   if (nodes[idx].L == nodes[idx].R) {
      if (nodes[idx].L >= from)
         nodes[idx].id = id;
      else {
         nodes[idx].id = -1;
         assign_device_id(id, from);
      }
      return;
   }
   nodes[idx].flipped = !nodes[idx].flipped;
   if (nodes[idx].flipped)
      assign_device_id(id, from, 2*idx);
   else
      assign_device_id(id, from, 2*idx+1);
}

void compress_tree(int idx = 1) {
    if (nodes[idx].L == nodes[idx].R)
       return;

    compress_tree(idx*2);
    compress_tree(idx*2 + 1);
    if (nodes[idx*2].leaf && nodes[idx*2+1].leaf && 
        nodes[idx*2].id == nodes[idx*2+1].id) {
        nodes[idx].leaf = true;
        nodes[idx].id = nodes[idx*2].id;
    }
}

void reassign_switch_ids(map<int,int>& reassigned_ids,
                         int& last_switch_id, int idx = 1) {
    int id = nodes[idx].id;
    if (id < 0) {
        if (reassigned_ids.count(id))
            nodes[idx].id = reassigned_ids[id];
        else {
            last_switch_id++;
            nodes[idx].id = reassigned_ids[id] = -last_switch_id;
        }
    }
    if (nodes[idx].leaf)
        return;
    if (nodes[idx].L == nodes[idx].R)
       return;
    reassign_switch_ids(reassigned_ids, last_switch_id, idx*2);
    reassign_switch_ids(reassigned_ids, last_switch_id, idx*2 + 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].leaf) return;
   int id = nodes[idx].id;
   if (id < 0) {
      id = -(id+1);
      switches[ id ].x = nodes[idx*2  ].id;
      switches[ id ].y = nodes[idx*2+1].id;
   }
   assign_switch_exits(idx*2);
   assign_switch_exits(idx*2 + 1);
}


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

   if (count(nxt.begin(), nxt.end(), nxt[0]) == K)
      return nxt[0];
 
   int nodes_last_level = 1;
   while (nodes_last_level < K)
      nodes_last_level *= 2;
 
   nodes = vector<Node>(2*nodes_last_level);

   build_tree(1, 0, nodes_last_level-1);
 
   int from = nodes_last_level - K;
   for (int dev_id : nxt)
      assign_device_id(dev_id, from);

   /*
   fprintf(stderr, "src: %d\n", src);
   fprintf(stderr, "nodes_last_level:%d  K:%d\n", nodes_last_level, K);
   */

   /*
   fprintf(stderr, "After assigned device ids\n");
   for (int idx = 1; idx < int(nodes.size()); ++idx) {
      Node x = nodes[idx];
      fprintf(stderr, "%3d  [%d,%d]  id:%d  leaf:%d\n", idx, x.L, x.R, x.id, x.leaf);
   }
   fprintf(stderr, "\n");
   */
 
   compress_tree();

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

   int last_switch_id = switches.size();
   map<int,int> reassigned_ids;
   reassign_switch_ids(reassigned_ids, last_switch_id);

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

   // fprintf(stderr, "last_switch_id:%d\n", last_switch_id);
   switches.resize( last_switch_id );

   assign_switch_exits();
   // fprintf(stderr, "END\n\n"); 

   return nodes[1].id;
}
 
}
 
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;
   // fprintf(stderr, "j:%d  x:%d  y:%d\n", j, X[j], Y[j]);
   }
   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.553352349600004 / 56