oj.uz

Submission #646224

# Submission time Handle Problem Language Result Execution time Memory
646224 2022-09-29T09:06:42 Z slime Mechanical Doll (IOI18_doll) C++14
68.6055 / 100
 177 ms 30980 KB 
#include "doll.h"
#include "bits/stdc++.h"
using namespace std;

void create_circuit(int M, std::vector<int> A);

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);

int lg(int x) {
  return 32 - __builtin_clz(x) - 1;
}
vector<int> X, Y;
int sub = 0;

pair<bool, int> dfs(int node, int prv) { // fake id
  int S = X.size();
  int rr;
  bool gd = 1;
  if(X[node] >= -1) {
    rr = X[node];
  }
  else {
    pair<bool, int> left = dfs(-(X[node] + 1), node);
    gd &= left.first;
    rr = left.second;
  }
  if(Y[node] >= -1) {
    gd &= (rr == Y[node]);
  }
  else {
    pair<bool, int> right = dfs(-(Y[node] + 1), node);
    gd &= right.first;
    gd &= (rr == right.second);
  }
  if(gd && prv != -1) {
    if(-(X[prv] + 1) == node) X[prv] = rr;
    else Y[prv] = rr;
    sub++;
  }
  return {gd, rr};
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  int freq[M + 1];
  for(int i=0; i<=M; i++) freq[i] = 0;
  for(int i=0; i<N; i++) freq[A[i]]++;
  freq[0]++;
  vector<int> C(M + 1);
  for(int i=0; i<=M; i++) C[i] = 0;
  C[0] = A[0];
  vector<int> sequence;
  for(int i=0; i<N; i++) {
    if(freq[A[i]] == 1) {
      C[A[i]] = (i+1 == N ? 0 : A[i+1]);
    }
    else {
      sequence.push_back((i+1 == N ? 0 : A[i+1]));
      C[A[i]] = -1;
    }
  }

  if(sequence.empty()) {
    answer(C, sequence, sequence);
    return;
  }
  
  int len = sequence.size();

  while((1 << lg(len)) != len) {
    sequence.push_back(-1);
    swap(sequence[sequence.size() - 2], sequence[sequence.size() - 1]);
    len++;
  }

  len = sequence.size();
  int cnt = 0;
  for(int x: sequence) cnt += (x == -1);

  vector<int> cpy = sequence;
  vector<int> ord;
  for(int x: sequence) if(x != -1) ord.push_back(x);
  int id = 0;
  for(int i=0; i<len; i++) {
    if(i%2 == 1 && cnt > 0) {
      cnt--;
      sequence[i] = -1;
    }
    else {
      sequence[i] = ord[id++];
    }
  }

  //for(int x: sequence) cout << x << " ";
  //cout << "\n";

  int layers = lg(len);

  
  X.resize((1 << layers) - 1);
  Y.resize((1 << layers) - 1);

  for(int i=0; i<(1 << layers) - 1; i++) {
    if(2*i+1 < (1<<layers) - 1) X[i] = -(2*i+1 + 1);
    if(2*i+2 < (1<<layers) - 1) Y[i] = -(2*i+2 + 1);
  }
  for(int i=0; i<len; i++) {
    int cp = 0;
    string str;
    for(int j=0; j<lg(len)-1; j++) {
      if(i & (1<<j)) {
        cp = cp * 2 + 2;
        str += "Y";
      }
      else {
        cp = cp * 2 + 1;
        str += "X";
      }
    }
    if(i & (1 << (lg(len) - 1))) {
      str += "Y";
      Y[cp] = sequence[i];
    }
    else {
      str += "X";
      X[cp] = sequence[i];
    }
    //cout << cp << " " << str << "\n";
  }
  
  dfs(0, -1);

  queue<int> usable;
  unordered_map<int, int> par;
  for(int i=0; i<(1<<layers)-1; i++) par[-(X[i] + 1)] = par[-(Y[i] + 1)] = i;

  bool used[(1<<layers) - 1];
  for(int i=0; i<(1<<layers)-1; i++) used[i] = 1;
  for(int i=0; i<(1<<layers)-1; i++) {
    if(X[i] == Y[i]) {
      usable.push(i);
      used[i] = 0;
    }
    else if(usable.size()) {
      int ff = usable.front(); usable.pop();
      int gp = par[i];
      if(X[gp] == -(i+1)) X[gp] = -(ff+1);
      else Y[gp] = -(ff+1);
      X[ff] = X[i];
      Y[ff] = Y[i];
      used[i] = 0;
      used[ff] = 1;
      par[-(X[i] + 1)] = par[-(Y[i] + 1)] = ff;
      usable.push(i);
    }
  }

  for(int i=(1<<layers)-2; i>=0; i--) {
    if(!used[i]) {
      X.pop_back();
      Y.pop_back();
    }
  }
  

  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'std::pair<bool, int> dfs(int, int)':
doll.cpp:16:7: warning: unused variable 'S' [-Wunused-variable]
   16 |   int S = X.size();
      |       ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 15 ms 2772 KB Output is correct
3 Correct 12 ms 2292 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 8 ms 1836 KB Output is correct
6 Correct 18 ms 3284 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 15 ms 2772 KB Output is correct
3 Correct 12 ms 2292 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 8 ms 1836 KB Output is correct
6 Correct 18 ms 3284 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 94 ms 16952 KB Output is correct
9 Correct 97 ms 16744 KB Output is correct
10 Incorrect 177 ms 30980 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 15 ms 2772 KB Output is correct
3 Correct 12 ms 2292 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 8 ms 1836 KB Output is correct
6 Correct 18 ms 3284 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 94 ms 16952 KB Output is correct
9 Correct 97 ms 16744 KB Output is correct
10 Incorrect 177 ms 30980 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 46 ms 5420 KB Output is correct
3 Correct 75 ms 8200 KB Output is correct
4 Correct 127 ms 16396 KB Output is correct

Subtask #6
38.6055114368 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 46 ms 5420 KB Output is correct
3 Correct 75 ms 8200 KB Output is correct
4 Correct 127 ms 16396 KB Output is correct
5 Partially correct 160 ms 25408 KB Output is partially correct
6 Partially correct 149 ms 24512 KB Output is partially correct
7 Partially correct 157 ms 24800 KB Output is partially correct
8 Partially correct 150 ms 24064 KB Output is partially correct
9 Correct 104 ms 13552 KB Output is correct
10 Partially correct 148 ms 23232 KB Output is partially correct
11 Partially correct 143 ms 23484 KB Output is partially correct
12 Correct 109 ms 15136 KB Output is correct
13 Correct 80 ms 13040 KB Output is correct
14 Correct 118 ms 16032 KB Output is correct
15 Correct 118 ms 16420 KB Output is correct
16 Correct 3 ms 724 KB Output is correct
17 Correct 76 ms 12440 KB Output is correct
18 Correct 74 ms 12440 KB Output is correct
19 Correct 116 ms 15224 KB Output is correct
20 Partially correct 148 ms 23640 KB Output is partially correct
21 Partially correct 143 ms 23556 KB Output is partially correct
22 Partially correct 142 ms 23520 KB Output is partially correct