Advertisement
erek1e

IOI '18 - Doll (53pts)

Jul 27th, 2022
591
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.44 KB | None | 0 0
  1. #include "doll.h"
  2. #include <set>
  3. #include <tuple>
  4. #include <cassert>
  5. #include <iostream>
  6.  
  7. using namespace std;
  8.  
  9. const int INF = 1e9;
  10.  
  11. bool drain(int i, int root, vector<int> &X, vector<int> &Y) {
  12.   bool isDrain = false;
  13.   if (X[-i] < 0) {if (drain(X[-i], root, X, Y)) isDrain = true;}
  14.   else if (X[-i] == 0 || X[-i] == INF) X[-i] = root, isDrain = true;
  15.   if (Y[-i] < 0) {if (drain(Y[-i], root, X, Y)) isDrain = true;}
  16.   else if (Y[-i] == 0 || Y[-i] == INF) Y[-i] = root, isDrain = true;
  17.   return isDrain;
  18. }
  19.  
  20. void create_circuit(int M, vector<int> A) {
  21.   int N = A.size();
  22.   vector<vector<int>> nxt(1+M);
  23.   nxt[0].push_back(A[0]);
  24.   for (int i = 0; i < N-1; ++i) {
  25.     nxt[A[i]].push_back(A[i+1]);
  26.   }
  27.   nxt[A[N-1]].push_back(0);
  28.  
  29.   int S = 0;
  30.   vector<int> X(1), Y(1);
  31.   vector<int> C(1+M); // root switch for each trigger
  32.  
  33.   for (int i = 0; i <= M; ++i) {
  34.     if (nxt[i].empty()) { // unused trigger
  35.       C[i] = i;
  36.       continue;
  37.     }
  38.     int p2 = 1, expo = 0;
  39.     while (p2 < (int)nxt[i].size()) ++expo, p2 <<= 1;
  40.  
  41.     // Order targets (stored in nxt) for tree of switches
  42.     vector<int> orderedNxt(1, 0);
  43.     for (int j = 1, previousPow2 = 1; j <= expo; ++j, previousPow2 <<= 1) {
  44.       vector<int> nextLevel(2*orderedNxt.size());
  45.       for (int k = 0; k < (int)nextLevel.size(); ++k) {
  46.         nextLevel[k] = orderedNxt[k>>1] + (k&1)*previousPow2;
  47.       }
  48.       orderedNxt = nextLevel;
  49.     }
  50.     for (int j = 0; j < p2; ++j) {
  51.       if (orderedNxt[j] >= (int)nxt[i].size()) orderedNxt[j] = INF;
  52.       else orderedNxt[j] = nxt[i][orderedNxt[j]];
  53.     }
  54.  
  55.     // Now build switches for pairs of targets
  56.     vector<int> curSwitches = orderedNxt;
  57.     while (curSwitches.size() > 1) {
  58.       vector<int> nextSwitches((int)curSwitches.size()>>1);
  59.       for (int j = 0; j < (int)nextSwitches.size(); ++j) {
  60.         int x = curSwitches[2*j], y = curSwitches[2*j+1];
  61.         if (x==INF && y==INF) {// this should never happen
  62.           nextSwitches[j] = INF;
  63.           continue;
  64.         }
  65.         // create switch
  66.        
  67.         // Create new switch
  68.         ++S;
  69.         X.push_back(x);
  70.         Y.push_back(y);
  71.         nextSwitches[j] = -S;
  72.       }
  73.       curSwitches = nextSwitches;
  74.     }
  75.  
  76.     // now curSwitches[0] is the root switch for this trigger
  77.     C[i] = curSwitches[0];
  78.   }
  79.  
  80.   // Now we need to "drain" the switches at the end so they all have state X at the end
  81.   //  find the roots of the trees that need draining
  82.   vector<int> needDrain;
  83.   for (int i = 0; i <= M; ++i) {
  84.     if (C[i] >= 0) {
  85.       if (C[i] == 0 || C[i] == INF) C[i] = i;
  86.     } else if (drain(C[i], C[i], X, Y) && i != A[N-1]) {
  87.       needDrain.push_back(i);
  88.     }
  89.   }
  90.  
  91.   auto getBottom = [&C, &Y](int i) {
  92.     int root = C[i]; i = C[i];
  93.     while (true) {
  94.       if (i > 0) {
  95.         if (C[i] == root) return i;
  96.         i = C[i];
  97.       } else {
  98.         if (Y[-i] == root) return i;
  99.         i = Y[-i];
  100.       }
  101.     }
  102.   };
  103.  
  104.   //  link up the drain chain drain chain
  105.   int prevBottom = getBottom(A[N-1]);
  106.   for (int i : needDrain) {
  107.     // connect bottom (end) of previous to root of current
  108.     if (prevBottom > 0) C[prevBottom] = C[i];
  109.     else Y[-prevBottom] = C[i];
  110.     // find bottom of current
  111.     prevBottom = getBottom(i);
  112.   }
  113.  
  114.   //   connect last bottom back to the origin
  115.   if (prevBottom > 0) C[prevBottom] = 0;
  116.   else Y[-prevBottom] = 0;
  117.  
  118.   X.erase(X.begin());
  119.   Y.erase(Y.begin());
  120.   answer(C, X, Y);
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement