oj.uz

Submission #830154

# Submission time Handle Problem Language Result Execution time Memory
830154 2023-08-18T20:17:09 Z radaiosm7 Mechanical Doll (IOI18_doll) C++17
53 / 100
 113 ms 22496 KB 
#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();
  C.resize(m+1);
  s = 0;
  A.push_back(0);
  for (i=0; i < n; ++i) adj[A[i]].push_back(A[i+1]);
  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 2 ms 2644 KB Output is correct
2 Correct 18 ms 6748 KB Output is correct
3 Correct 16 ms 6580 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 10 ms 4012 KB Output is correct
6 Correct 24 ms 8588 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 2 ms 2644 KB Output is correct
2 Correct 18 ms 6748 KB Output is correct
3 Correct 16 ms 6580 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 10 ms 4012 KB Output is correct
6 Correct 24 ms 8588 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 34 ms 10096 KB Output is correct
9 Correct 38 ms 10428 KB Output is correct
10 Correct 52 ms 14044 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 2660 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 18 ms 6748 KB Output is correct
3 Correct 16 ms 6580 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 10 ms 4012 KB Output is correct
6 Correct 24 ms 8588 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 34 ms 10096 KB Output is correct
9 Correct 38 ms 10428 KB Output is correct
10 Correct 52 ms 14044 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 2660 KB Output is correct
14 Correct 75 ms 16848 KB Output is correct
15 Correct 36 ms 9808 KB Output is correct
16 Correct 53 ms 13900 KB Output is correct
17 Correct 1 ms 2644 KB Output is correct
18 Correct 1 ms 2656 KB Output is correct
19 Correct 1 ms 2644 KB Output is correct
20 Correct 60 ms 15396 KB Output is correct
21 Correct 1 ms 2660 KB Output is correct
22 Correct 1 ms 2644 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2644 KB Output is partially correct
2 Correct 45 ms 11804 KB Output is correct
3 Partially correct 83 ms 18552 KB Output is partially correct
4 Partially correct 90 ms 19492 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2644 KB Output is partially correct
2 Correct 45 ms 11804 KB Output is correct
3 Partially correct 83 ms 18552 KB Output is partially correct
4 Partially correct 90 ms 19492 KB Output is partially correct
5 Partially correct 75 ms 17296 KB Output is partially correct
6 Partially correct 80 ms 18576 KB Output is partially correct
7 Partially correct 80 ms 18196 KB Output is partially correct
8 Partially correct 82 ms 19216 KB Output is partially correct
9 Partially correct 90 ms 16216 KB Output is partially correct
10 Partially correct 113 ms 22496 KB Output is partially correct
11 Partially correct 102 ms 20024 KB Output is partially correct
12 Partially correct 66 ms 14060 KB Output is partially correct
13 Partially correct 54 ms 12932 KB Output is partially correct
14 Partially correct 52 ms 12588 KB Output is partially correct
15 Partially correct 50 ms 12084 KB Output is partially correct
16 Partially correct 3 ms 2900 KB Output is partially correct
17 Partially correct 45 ms 11608 KB Output is partially correct
18 Partially correct 56 ms 11588 KB Output is partially correct
19 Partially correct 60 ms 12276 KB Output is partially correct
20 Partially correct 64 ms 15184 KB Output is partially correct
21 Partially correct 92 ms 17664 KB Output is partially correct
22 Partially correct 59 ms 15188 KB Output is partially correct