oj.uz

답안 #646236

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
646236 2022-09-29T09:21:03 Z slime 자동 인형 (IOI18_doll) C++14
57.1539 / 100
 155 ms 15152 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]));
      C[A[x]] = -(X.size() + 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();
      }
    }

    


    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]);
    }
    
  }
  

  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 15 ms 2388 KB Output is correct
3 Correct 13 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 2620 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 15 ms 2388 KB Output is correct
3 Correct 13 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 2620 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 79 ms 7980 KB wrong motion
9 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 15 ms 2388 KB Output is correct
3 Correct 13 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 2620 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 79 ms 7980 KB wrong motion
9 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB wrong serial number
9 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 46 ms 5048 KB Output is correct
3 Correct 74 ms 7764 KB Output is correct
4 Correct 123 ms 15152 KB Output is correct

Subtask #6
37.153865896 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 46 ms 5048 KB Output is correct
3 Correct 74 ms 7764 KB Output is correct
4 Correct 123 ms 15152 KB Output is correct
5 Partially correct 148 ms 12028 KB Output is partially correct
6 Partially correct 145 ms 11656 KB Output is partially correct
7 Partially correct 146 ms 11820 KB Output is partially correct
8 Partially correct 144 ms 10932 KB Output is partially correct
9 Correct 108 ms 9012 KB Output is correct
10 Correct 155 ms 12308 KB Output is correct
11 Partially correct 151 ms 9692 KB Output is partially correct
12 Partially correct 99 ms 6664 KB Output is partially correct
13 Partially correct 95 ms 7908 KB Output is partially correct
14 Partially correct 96 ms 7980 KB Output is partially correct
15 Partially correct 97 ms 8232 KB Output is partially correct
16 Partially correct 3 ms 568 KB Output is partially correct
17 Partially correct 91 ms 7152 KB Output is partially correct
18 Partially correct 85 ms 6916 KB Output is partially correct
19 Partially correct 106 ms 7500 KB Output is partially correct
20 Partially correct 124 ms 9952 KB Output is partially correct
21 Partially correct 152 ms 11004 KB Output is partially correct
22 Partially correct 130 ms 10800 KB Output is partially correct