Submission #829545

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
829545	2023-08-18T12:32:09 Z	radaiosm7	Mechanical Doll (IOI18_doll)	C++17	16 / 100	1000 ms	14636 KB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
int i, n, m, s, g, j, kk;
vector<int> C;
vector<int> X;
vector<int> Y;
vector<int> adj[100005];
bool visited[100005];
bool finished[200005];
vector<vector<int> > groups;
vector<int> tmp;
bool vis;
vector<int> sw;
vector<int> st;
vector<pair<int, int> > pos;

void new_switch() {
  sw.push_back(--s);
  st.push_back(0);
  X.push_back(sw.front());
  Y.push_back(sw.front());
}

void dfs(int x) {
  if (st[-x-1] == 0) {
    st[-x-1] ^= 1;
    if (X[-x-1] == sw.front()) pos.push_back(make_pair(-x-1, 0));
    else dfs(X[-x-1]);
  }

  else {
    st[-x-1] ^= 1;
    if (Y[-x-1] == sw.front()) pos.push_back(make_pair(-x-1, 1));
    else dfs(Y[-x-1]);
  }
}

void create_switch(int i) {
  int num = (int)adj[i].size();
  if (num == 0) C[i] = i;

  else if (num == 1) C[i] = adj[i][0];

  else {
    sw.clear();

    kk = 1;
    while (kk < num) kk *= 2;
    --kk;

    new_switch();
    C[i] = s;

    for (int j=1; j < kk; ++j) {
      new_switch();
      if (j&1) X[-sw[j>>1]-1] = s;
      else Y[-sw[(j-1)>>1]-1] = s;
    }

    pos.clear();
    for (int j=0; j <= kk; ++j) dfs(sw.front());

    for (j=num-1; j >= 0; --j) {
      if (pos[kk].second == 0) X[pos[kk].first] = adj[i][j];
      else Y[pos[kk].first] = adj[i][j];
      --kk;
    }
  }
}

void create_circuit(int M, vector<int> A) {
  m = M;
  n = (int)A.size();
  fill(finished, finished+n+1, false);
  C.resize(M+1);
  X.clear();
  Y.clear();
  st.clear();
  s = 0;

  do {
    vis = false;
    tmp.clear();
    fill(visited, visited+m+1, false);

    for (i=0; i < n-1; ++i) {
      if (!finished[i] && !visited[A[i]]) {
        finished[i] = true;
        visited[A[i]] = true;
        tmp.push_back(i);
        vis = true;
      }
    }

    groups.push_back(tmp);
  } while(vis);

  g = (int)groups.size();

  for (i=0; i < g; ++i) {
    kk = (int)groups[i].size();
    for (j=0; j < kk; ++j) adj[A[groups[i][j]]].push_back(A[groups[i][j]+1]);
  }

  adj[A[n-1]].push_back(0);
  
  C[0] = A[0];
  for (i=1; i <= M; ++i) create_switch(i);
  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2644 KB	Output is correct
2	Correct	24 ms	7020 KB	Output is correct
3	Correct	16 ms	6640 KB	Output is correct
4	Correct	1 ms	2644 KB	Output is correct
5	Correct	11 ms	4044 KB	Output is correct
6	Correct	24 ms	8652 KB	Output is correct
7	Correct	1 ms	2616 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2644 KB	Output is correct
2	Correct	24 ms	7020 KB	Output is correct
3	Correct	16 ms	6640 KB	Output is correct
4	Correct	1 ms	2644 KB	Output is correct
5	Correct	11 ms	4044 KB	Output is correct
6	Correct	24 ms	8652 KB	Output is correct
7	Correct	1 ms	2616 KB	Output is correct
8	Correct	39 ms	10168 KB	Output is correct
9	Correct	39 ms	10304 KB	Output is correct
10	Correct	72 ms	12836 KB	Output is correct
11	Correct	1 ms	2644 KB	Output is correct
12	Correct	1 ms	2644 KB	Output is correct
13	Correct	1 ms	2644 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2644 KB	Output is correct
2	Correct	24 ms	7020 KB	Output is correct
3	Correct	16 ms	6640 KB	Output is correct
4	Correct	1 ms	2644 KB	Output is correct
5	Correct	11 ms	4044 KB	Output is correct
6	Correct	24 ms	8652 KB	Output is correct
7	Correct	1 ms	2616 KB	Output is correct
8	Correct	39 ms	10168 KB	Output is correct
9	Correct	39 ms	10304 KB	Output is correct
10	Correct	72 ms	12836 KB	Output is correct
11	Correct	1 ms	2644 KB	Output is correct
12	Correct	1 ms	2644 KB	Output is correct
13	Correct	1 ms	2644 KB	Output is correct
14	Correct	72 ms	14636 KB	Output is correct
15	Correct	37 ms	9044 KB	Output is correct
16	Correct	59 ms	12132 KB	Output is correct
17	Correct	1 ms	2644 KB	Output is correct
18	Correct	1 ms	2644 KB	Output is correct
19	Correct	2 ms	2644 KB	Output is correct
20	Correct	68 ms	13828 KB	Output is correct
21	Correct	1 ms	2644 KB	Output is correct
22	Correct	1 ms	2644 KB	Output is correct