oj.uz

Submission #646237

# Submission time Handle Problem Language Result Execution time Memory
646237 2022-09-29T09:28:04 Z slime Mechanical Doll (IOI18_doll) C++14
81.1539 / 100
 150 ms 15020 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();
    int oo = X.size();
    C[element] = -(oo + 1);
    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();
      }
    }

    if(tempX.empty()) {
      int ind = list[element][0];
      C[element] = (ind + 1 == N ? 0 :A[ind + 1]);
      continue;
    }


    int uwu = tempX.size();
    int sm = X.size();
    for(int i=0; i<uwu; i++) {
      if(tempX[i] < 0) tempX[i] -= sm;
      if(tempY[i] < 0) tempY[i] -= sm;

      X.push_back(tempX[i]);
      Y.push_back(tempY[i]);
      //cout << tempX[i] << " " << tempY[i] << "\n";
    }
    
  }
  

  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 15 ms 2388 KB Output is correct
3 Correct 12 ms 1748 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1748 KB Output is correct
6 Correct 18 ms 2644 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 15 ms 2388 KB Output is correct
3 Correct 12 ms 1748 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1748 KB Output is correct
6 Correct 18 ms 2644 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 65 ms 7972 KB Output is correct
9 Correct 68 ms 9580 KB Output is correct
10 Correct 102 ms 12792 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 15 ms 2388 KB Output is correct
3 Correct 12 ms 1748 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1748 KB Output is correct
6 Correct 18 ms 2644 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 65 ms 7972 KB Output is correct
9 Correct 68 ms 9580 KB Output is correct
10 Correct 102 ms 12792 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 124 ms 13532 KB Output is correct
15 Correct 66 ms 7764 KB Output is correct
16 Correct 97 ms 11144 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 300 KB Output is correct
20 Correct 125 ms 13148 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 5048 KB Output is correct
3 Correct 80 ms 7720 KB Output is correct
4 Correct 134 ms 15020 KB Output is correct

Subtask #6
37.153865896 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 46 ms 5048 KB Output is correct
3 Correct 80 ms 7720 KB Output is correct
4 Correct 134 ms 15020 KB Output is correct
5 Partially correct 139 ms 12000 KB Output is partially correct
6 Partially correct 138 ms 11240 KB Output is partially correct
7 Partially correct 134 ms 11464 KB Output is partially correct
8 Partially correct 135 ms 10460 KB Output is partially correct
9 Correct 99 ms 8632 KB Output is correct
10 Correct 150 ms 11880 KB Output is correct
11 Partially correct 147 ms 9320 KB Output is partially correct
12 Partially correct 96 ms 6276 KB Output is partially correct
13 Partially correct 87 ms 7512 KB Output is partially correct
14 Partially correct 96 ms 7628 KB Output is partially correct
15 Partially correct 81 ms 7944 KB Output is partially correct
16 Partially correct 3 ms 468 KB Output is partially correct
17 Partially correct 91 ms 6728 KB Output is partially correct
18 Partially correct 87 ms 6652 KB Output is partially correct
19 Partially correct 96 ms 7120 KB Output is partially correct
20 Partially correct 121 ms 9564 KB Output is partially correct
21 Partially correct 146 ms 10696 KB Output is partially correct
22 Partially correct 123 ms 10432 KB Output is partially correct