Submission #333141

#	Time	Username	Problem	Language	Result	Execution time	Memory
333141		couplefire	Mechanical Doll (IOI18_doll)	C++17	6 / 100	157 ms	58528 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000009

struct Switch{
    int cur = 0;
    vector<int> ch = {-INF, -INF};
    Switch(){}
};

struct Trigger{
    int next = -INF;
    Trigger(){}
};

void create_circuit(int m, vector<int> events) {
  events.push_back(0);
  int n = events.size();
  vector<int> cnt(m+1, 0);
  for(int i = 0; i<n; i++) cnt[events[i]]++;
  vector<Trigger> triggers(m+1);
//   cout << n << endl;
  vector<Switch> switches(2*n);
//   cout << 1 << endl;
  vector<int> par(2*n);
//   cout << 1 << endl;
  int curSwitch = 1;
  for(int i = 0; i<=m; i++){
      if(cnt[i] == 1) continue;
      if(cnt[i] == 0){
          triggers[i].next = 0;
          continue;
      }
      queue<int> q;
      triggers[i].next = -curSwitch;
      par[curSwitch] = i;
      q.push(curSwitch++);
      int curCnt = 2;
      while(curCnt < cnt[i]){
          int s = q.front();
          q.pop();
          switches[s].ch[0] = -(curSwitch++);
          switches[s].ch[1] = -(curSwitch++);
          curCnt += 2;
          q.push(-switches[s].ch[0]);
          q.push(-switches[s].ch[1]);
          par[-switches[s].ch[0]] = -s;
          par[-switches[s].ch[1]] = -s;
      }
  }
  stack<int> st;
  st.push(0);
  int ind = 0;
  bool lol = false;
  while(ind < n){
      int v = st.top();
      st.pop();
      if(v >= 0){
          if(triggers[v].next == -INF) triggers[v].next = events[ind];
          if(triggers[v].next == events[ind]) ind++;
          st.push(triggers[v].next);
      }
      else{
          v = -v;
          if(switches[v].ch[switches[v].cur] == -INF) switches[v].ch[switches[v].cur] = events[ind];
          if(switches[v].ch[switches[v].cur] == events[ind]){
              if(ind != n-1 || par[v] >= 0 || lol || switches[par[v]].ch[1] == v) ind++;
              else{
                  switches[v].ch[switches[v].cur] = par[v];
                  lol = true;
              }
          }
          st.push(switches[v].ch[switches[v].cur]);
          switches[v].cur = 1-switches[v].cur;
      }
    //   cout << n-ind << endl;
  }
//   cout << switches[0].next << endl;
  vector<int> C, X, Y;
  C.resize(m+1);
  for(int i = 1; i<curSwitch; i++){
      X.push_back(switches[i].ch[0]);
      Y.push_back(switches[i].ch[1]);
  }
  for(int i = 0; i<=m; i++) C[i] = triggers[i].next;
  answer(C, X, Y);
}

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