Submission #829482

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
829482	2023-08-18T11:16:08 Z	radaiosm7	Mechanical Doll (IOI18_doll)	C++17	16 / 100	71 ms	15064 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;

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 {
    --s;
    C[i] = s;
    
    if (num == 2) {
      X.push_back(adj[i][0]);
      Y.push_back(adj[i][1]);
    }

    else if (num == 3) {
      X.push_back(--s);
      Y.push_back(--s);
      X.push_back(adj[i][0]);
      Y.push_back(C[i]);
      X.push_back(adj[i][1]);
      Y.push_back(adj[i][2]);
    }

    else if (num == 4) {
      X.push_back(--s);
      Y.push_back(--s);
      X.push_back(adj[i][0]);
      Y.push_back(adj[i][2]);
      X.push_back(adj[i][1]);
      Y.push_back(adj[i][3]);
    }
  }
}

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();
  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	18 ms	6992 KB	Output is correct
3	Correct	16 ms	6608 KB	Output is correct
4	Correct	1 ms	2644 KB	Output is correct
5	Correct	9 ms	4112 KB	Output is correct
6	Correct	27 ms	8652 KB	Output is correct
7	Correct	1 ms	2644 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	18 ms	6992 KB	Output is correct
3	Correct	16 ms	6608 KB	Output is correct
4	Correct	1 ms	2644 KB	Output is correct
5	Correct	9 ms	4112 KB	Output is correct
6	Correct	27 ms	8652 KB	Output is correct
7	Correct	1 ms	2644 KB	Output is correct
8	Correct	45 ms	9788 KB	Output is correct
9	Correct	38 ms	9928 KB	Output is correct
10	Correct	52 ms	12772 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	18 ms	6992 KB	Output is correct
3	Correct	16 ms	6608 KB	Output is correct
4	Correct	1 ms	2644 KB	Output is correct
5	Correct	9 ms	4112 KB	Output is correct
6	Correct	27 ms	8652 KB	Output is correct
7	Correct	1 ms	2644 KB	Output is correct
8	Correct	45 ms	9788 KB	Output is correct
9	Correct	38 ms	9928 KB	Output is correct
10	Correct	52 ms	12772 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	65 ms	14652 KB	Output is correct
15	Correct	36 ms	9184 KB	Output is correct
16	Correct	56 ms	12840 KB	Output is correct
17	Correct	2 ms	2644 KB	Output is correct
18	Correct	2 ms	2664 KB	Output is correct
19	Correct	1 ms	2644 KB	Output is correct
20	Correct	71 ms	15064 KB	Output is correct
21	Correct	1 ms	2644 KB	Output is correct
22	Correct	1 ms	2664 KB	Output is correct