oj.uz

답안 #993568

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
993568 2024-06-06T05:05:58 Z poqmen 자동 인형 (IOI18_doll) C++14
100 / 100
 84 ms 9556 KB 
#include "doll.h"

#include <bits/stdc++.h>
using namespace std;

const int START_SENTINEL = 0xdeadbeef;
const int ROOT_SENTINEL = 0x15571557;

void create_circuit(int m, vector<int> a) {
  int n = a.size();
  vector<int> x, y;
  auto add_switch = [&](int sx, int sy) {
    x.push_back(sx);
    y.push_back(sy);
    return -x.size();
  };
  // returns root
  function<int(int, int, int)> construct_t_pow = [&](int sz, int off,
                                                     int stride) -> int {
    if (sz == 1) {
      return off;
    } else {
      int l = construct_t_pow(sz / 2, off, 2 * stride);
      int r = construct_t_pow(sz / 2, off + stride, 2 * stride);
      return add_switch(l, r);
    }
  };
  function<int(int, int, int, int)> construct_t = [&](int sz, int csz, int off,
                                                      int stride) -> int {
    if (csz == sz) {
      return construct_t_pow(csz, off, stride);
    }
    if (csz == 1 && sz == 0) return 0;  // the zero-node
    if ((csz / 2) & sz) {
      int l = construct_t_pow(csz / 2, off, 2 * stride);
      int r = construct_t(sz - (csz / 2), csz / 2, off + stride, 2 * stride);
      return add_switch(l, r);
    } else {
      int l = ROOT_SENTINEL;  // the root
      int r = construct_t(sz, csz / 2, off + stride, 2 * stride);
      return add_switch(l, r);
    }
  };
  int csz = 2 << __lg(n);
  int root = construct_t(n, csz, 1, 1);
  vector<int> indices;
  for (int i = 0; i < x.size(); ++i) {
    if (x[i] == ROOT_SENTINEL) x[i] = root;
    if (y[i] == ROOT_SENTINEL) y[i] = root;
    if (x[i] > 0) indices.push_back(x[i]);
    if (y[i] > 0) indices.push_back(y[i]);
  }
  sort(indices.begin(), indices.end());
  for (int i = 0; i < x.size(); ++i) {
    if (x[i] > 0)
      x[i] = a[lower_bound(indices.begin(), indices.end(), x[i]) -
               indices.begin()];
    if (y[i] > 0)
      y[i] = a[lower_bound(indices.begin(), indices.end(), y[i]) -
               indices.begin()];
  }
  answer(vector<int>(m + 1, root), x, y);
  return;
}

#ifndef EVAL
#include "grader.cpp"
#endif

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int i = 0; i < x.size(); ++i) {
      |                   ~~^~~~~~~~~~
doll.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (int i = 0; i < x.size(); ++i) {
      |                   ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 26 ms 4404 KB Output is correct
3 Correct 25 ms 3904 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1236 KB Output is correct
6 Correct 40 ms 5444 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 26 ms 4404 KB Output is correct
3 Correct 25 ms 3904 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1236 KB Output is correct
6 Correct 40 ms 5444 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 50 ms 7348 KB Output is correct
9 Correct 55 ms 6988 KB Output is correct
10 Correct 73 ms 9556 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 26 ms 4404 KB Output is correct
3 Correct 25 ms 3904 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1236 KB Output is correct
6 Correct 40 ms 5444 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 50 ms 7348 KB Output is correct
9 Correct 55 ms 6988 KB Output is correct
10 Correct 73 ms 9556 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 72 ms 9280 KB Output is correct
15 Correct 47 ms 6208 KB Output is correct
16 Correct 69 ms 9280 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 84 ms 9376 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 44 ms 6256 KB Output is correct
3 Correct 44 ms 5960 KB Output is correct
4 Correct 78 ms 9020 KB Output is correct

Subtask #6
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 44 ms 6256 KB Output is correct
3 Correct 44 ms 5960 KB Output is correct
4 Correct 78 ms 9020 KB Output is correct
5 Correct 79 ms 9020 KB Output is correct
6 Correct 77 ms 9024 KB Output is correct
7 Correct 70 ms 9024 KB Output is correct
8 Correct 65 ms 9024 KB Output is correct
9 Correct 45 ms 5960 KB Output is correct
10 Correct 66 ms 9020 KB Output is correct
11 Correct 66 ms 9020 KB Output is correct
12 Correct 45 ms 5944 KB Output is correct
13 Correct 46 ms 6576 KB Output is correct
14 Correct 50 ms 6132 KB Output is correct
15 Correct 49 ms 6132 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 43 ms 5960 KB Output is correct
18 Correct 44 ms 6336 KB Output is correct
19 Correct 45 ms 5952 KB Output is correct
20 Correct 67 ms 9024 KB Output is correct
21 Correct 68 ms 9036 KB Output is correct
22 Correct 84 ms 9020 KB Output is correct