oj.uz

Submission #646232

# Submission time Handle Problem Language Result Execution time Memory
646232 2022-09-29T09:16:54 Z slime Mechanical Doll (IOI18_doll) C++14
20 / 100
 127 ms 15064 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> tempX, tempY;

pair<bool, int> dfs(int node, int prv) { // fake id
  int rr;
  bool gd = 1;
  if(tempX[node] >= -1) {
    rr = tempX[node];
  }
  else {
    pair<bool, int> left = dfs(-(tempX[node] + 1), node);
    gd &= left.first;
    rr = left.second;
  }
  if(tempY[node] >= -1) {
    gd &= (rr == tempY[node]);
  }
  else {
    pair<bool, int> right = dfs(-(tempY[node] + 1), node);
    gd &= right.first;
    gd &= (rr == right.second);
  }
  if(gd && prv != -1) {
    if(-(tempX[prv] + 1) == node) tempX[prv] = rr;
    else tempY[prv] = rr;
  }
  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;
  }
  // Actual problem

  vector<int> list[M+1];
  for(int i=0; i<N; i++) {
    list[A[i]].push_back(i);
  }

  vector<int> X, Y;

  for(int element=1; element<=M; element++) {
    if(freq[element] == 1) continue;
    sequence.clear();
    tempX.clear();
    tempY.clear();
    for(int x: list[element]) {
      sequence.push_back((x+1 == N ? 0 : A[x+1]));
    }
  
    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);

    
    tempX.resize((1 << layers) - 1);
    tempY.resize((1 << layers) - 1);

    for(int i=0; i<(1 << layers) - 1; i++) {
      if(2*i+1 < (1<<layers) - 1) tempX[i] = -(2*i+1 + 1);
      if(2*i+2 < (1<<layers) - 1) tempY[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";
        tempY[cp] = sequence[i];
      }
      else {
        str += "X";
        tempX[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[-(tempX[i] + 1)] = par[-(tempY[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(tempX[i] == tempY[i]) {
        usable.push(i);
        used[i] = 0;
      }
      else if(usable.size()) {
        int ff = usable.front(); usable.pop();
        int gp = par[i];
        if(tempX[gp] == -(i+1)) tempX[gp] = -(ff+1);
        else tempY[gp] = -(ff+1);
        tempX[ff] = tempX[i];
        tempY[ff] = tempY[i];
        used[i] = 0;
        used[ff] = 1;
        par[-(tempX[i] + 1)] = par[-(tempY[i] + 1)] = ff;
        usable.push(i);
      }
    }

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

    X = tempX;
    Y = tempY;
  }
  

  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 20 ms 2628 KB Output is correct
3 Correct 21 ms 2056 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1748 KB Output is correct
6 Correct 20 ms 2920 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 20 ms 2628 KB Output is correct
3 Correct 21 ms 2056 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1748 KB Output is correct
6 Correct 20 ms 2920 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 70 ms 6656 KB wrong motion
9 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 20 ms 2628 KB Output is correct
3 Correct 21 ms 2056 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1748 KB Output is correct
6 Correct 20 ms 2920 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 70 ms 6656 KB wrong motion
9 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 49 ms 5392 KB Output is correct
3 Correct 79 ms 8092 KB Output is correct
4 Correct 127 ms 15064 KB Output is correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 49 ms 5392 KB Output is correct
3 Correct 79 ms 8092 KB Output is correct
4 Correct 127 ms 15064 KB Output is correct
5 Incorrect 111 ms 6780 KB wrong motion
6 Halted 0 ms 0 KB -