oj.uz

답안 #75396

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
75396 2018-09-09T14:53:02 Z Xellos 자동 인형 (IOI18_doll) C++14
100 / 100
 181 ms 16684 KB 
#include <bits/stdc++.h>
#include "doll.h"
#define ff first
#define ss second
using namespace std;

void create_circuit(int M, vector<int> A) {
  int N = A.size();
  int dep = 1;
  while((1<<dep) < N+1) dep++;
  vector< vector< pair<int, int> > > son[2];
  vector< vector<int> > state(dep);
  son[0].resize(dep);
  son[1].resize(dep);
  for(int i = 0; i < dep; i++) {
    state[i].resize(1<<i, 0);
    son[0][i].resize(1<<i, {i+1, -1});
    son[1][i].resize(1<<i, {i+1, -1});
    for(int j = 0; j < (1<<i); j++) {
      son[0][i][j].ss = 2*j;
      son[1][i][j].ss = 2*j+1;
    }
  }
  vector<int> order;
  for(int i = 0; i < (1<<dep); i++) {
    int cur = 0;
    for(int j = 0; j < dep; j++) {
      int nxt;
      if(state[j][cur]) nxt = son[1][j][cur].ss;
      else nxt = son[0][j][cur].ss;
      state[j][cur] ^= 1;
      cur = nxt;
    }
    order.push_back(cur);
  }
  vector<int> order_used;
  for(int i = 0; i < (1<<dep); i++) if(order[i] >= (1<<dep)-1-N) order_used.push_back(order[i]);
  order_used.push_back(order.back());
  vector< vector<int> > used(dep);
  for(int i = 0; i < dep; i++) used[i].resize(1<<i, 0);
  for(auto x: order_used) used[dep-1][x/2] = 1;
  for(int i = dep-2; i >= 0; i--) for(int j = 0; j < (1<<i); j++)
    if(used[i+1][2*j] || used[i+1][2*j+1]) used[i][j] = true;
  vector< vector<int> > id(dep);
  int S = 0;
  for(int i = 0; i < dep; i++) {
    id[i].resize(1<<i, -1);
    for(int j = 0; j < (1<<i); j++) if(used[i][j]) id[i][j] = S++;
  }
  vector<int> C(M+1, -1);
  vector<int> X(S, -1), Y(S, -1);
  for(int i = 0; i < dep-1; i++) for(int j = 0; j < (1<<i); j++) if(used[i][j]) {
    if(used[son[0][i][j].ff][son[0][i][j].ss]) X[id[i][j]] = -1-id[son[0][i][j].ff][son[0][i][j].ss];
    if(used[son[1][i][j].ff][son[1][i][j].ss]) Y[id[i][j]] = -1-id[son[1][i][j].ff][son[1][i][j].ss];
  }
  for(int i = 0; i <= N; i++) {
    int nxt = (i < N) ? A[i] : 0;
    int cur = order_used[i]/2;
    if(order_used[i]%2 == 0) X[id[dep-1][cur]] = nxt;
    else Y[id[dep-1][cur]] = nxt;
  }
  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 61 ms 7816 KB Output is correct
3 Correct 61 ms 7428 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 80 ms 9120 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 61 ms 7816 KB Output is correct
3 Correct 61 ms 7428 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 80 ms 9120 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 154 ms 13912 KB Output is correct
9 Correct 131 ms 14348 KB Output is correct
10 Correct 181 ms 16684 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 61 ms 7816 KB Output is correct
3 Correct 61 ms 7428 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 80 ms 9120 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 154 ms 13912 KB Output is correct
9 Correct 131 ms 14348 KB Output is correct
10 Correct 181 ms 16684 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 164 ms 16312 KB Output is correct
15 Correct 140 ms 13532 KB Output is correct
16 Correct 163 ms 16124 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 145 ms 16460 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 122 ms 13116 KB Output is correct
3 Correct 130 ms 13240 KB Output is correct
4 Correct 165 ms 15564 KB Output is correct

Subtask #6
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 122 ms 13116 KB Output is correct
3 Correct 130 ms 13240 KB Output is correct
4 Correct 165 ms 15564 KB Output is correct
5 Correct 162 ms 16052 KB Output is correct
6 Correct 157 ms 15748 KB Output is correct
7 Correct 150 ms 15848 KB Output is correct
8 Correct 158 ms 15812 KB Output is correct
9 Correct 171 ms 13148 KB Output is correct
10 Correct 152 ms 15656 KB Output is correct
11 Correct 151 ms 15588 KB Output is correct
12 Correct 116 ms 13092 KB Output is correct
13 Correct 146 ms 13240 KB Output is correct
14 Correct 117 ms 13348 KB Output is correct
15 Correct 131 ms 13440 KB Output is correct
16 Correct 5 ms 716 KB Output is correct
17 Correct 86 ms 9004 KB Output is correct
18 Correct 138 ms 13116 KB Output is correct
19 Correct 114 ms 13112 KB Output is correct
20 Correct 159 ms 15556 KB Output is correct
21 Correct 168 ms 15604 KB Output is correct
22 Correct 148 ms 15548 KB Output is correct