oj.uz

Submission #261165

# Submission time Handle Problem Language Result Execution time Memory
261165 2020-08-11T13:08:23 Z Nightlight Mechanical Doll (IOI18_doll) C++14
100 / 100
 131 ms 17428 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

int N, M;
int A[400005];
int tmp[400005];
int order[400005];
int to[400005];
int id[400005], pos[400005];
int X[400005], Y[400005];
int tot;
int cnt = 2;

void gen_order(int l, int r) {
  if(l == r) return void(pos[order[l]] = l);
  int mid = ((l + r) >> 1) + 1;
  for(int i = l; i <= r; i += 2) {
    tmp[l + (i - l) / 2] = order[i];
    tmp[mid + (i - l) / 2] = order[i + 1];
  }
  for(int i = l; i <= r; i++) order[i] = tmp[i];
  gen_order(l, mid - 1), gen_order(mid, r);
}

int DFS(int l, int r) {
  int now;
  if(l + 1 == r) {
    if(to[l] == to[r]) return to[l];
    if(l == 1 && r == tot) now = 1;
    else now = cnt++;
    X[now] = to[l], Y[now] = to[r];
//    cout << -now << " -> " << X[now] << " " << Y[now] << "\n";
    return -now;
  }
  int mid = (l + r) >> 1;
  int le = DFS(l, mid), ri = DFS(mid + 1, r);
  if(le == ri) return le;
  if(l == 1 && r == tot) now = 1;
  else now = cnt++;
  X[now] = le, Y[now] = ri;
//  cout << -now << " -> " << X[now] << " " << Y[now] << "\n";
  return -now;
}

void solve() {
  tot = log2(N);
//  cout << "tot -> " << tot << "\n";
  tot = (1 << tot);
  if(N > tot) tot <<= 1;
  for(int i = 1; i <= tot; i++) {
    order[i] = i;
  }
  gen_order(1, tot);
//  for(int i = 1; i <= tot; i++) cout << order[i] << " "; cout << "\n";
  memset(to, -1, sizeof(to));
  memset(tmp, -1, sizeof(tmp));
  for(int i = tot; i > tot - N; i--) tmp[order[i]] = 1;
  int p = 1;
  for(int i = 1; i <= tot; i++) {
    if(tmp[i] == -1) continue;
    to[pos[i]] = A[p++];
  }
//  assert(p == tot + 1);
  DFS(1, tot);
}

void create_circuit(int m, vector<int> a) {
  a.emplace_back(0);
  M = m, N = a.size();
  for(int i = 1; i <= N; i++) A[i] = a[i - 1];
  vector<int> c(M + 1);
  for(int i = 0; i <= M; i++) c[i] = -1;
  solve();
  vector<int> x(cnt - 1), y(cnt - 1);
  for(int i = 1; i < cnt; i++) {
    x[i - 1] = X[i];
//    assert(x[i - 1] <= m);
    y[i - 1] = Y[i];
//    assert(y[i - 1] <= m);
  }
  system("pause");
  answer(c, x, y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:83:9: warning: ignoring return value of 'int system(const char*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   system("pause");
      |   ~~~~~~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 42 ms 8520 KB Output is correct
3 Correct 42 ms 8748 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 15 ms 4552 KB Output is correct
6 Correct 55 ms 11088 KB Output is correct
7 Correct 4 ms 3404 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 42 ms 8520 KB Output is correct
3 Correct 42 ms 8748 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 15 ms 4552 KB Output is correct
6 Correct 55 ms 11088 KB Output is correct
7 Correct 4 ms 3404 KB Output is correct
8 Correct 71 ms 13220 KB Output is correct
9 Correct 72 ms 13752 KB Output is correct
10 Correct 99 ms 17428 KB Output is correct
11 Correct 4 ms 3404 KB Output is correct
12 Correct 3 ms 3404 KB Output is correct
13 Correct 3 ms 3404 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 42 ms 8520 KB Output is correct
3 Correct 42 ms 8748 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 15 ms 4552 KB Output is correct
6 Correct 55 ms 11088 KB Output is correct
7 Correct 4 ms 3404 KB Output is correct
8 Correct 71 ms 13220 KB Output is correct
9 Correct 72 ms 13752 KB Output is correct
10 Correct 99 ms 17428 KB Output is correct
11 Correct 4 ms 3404 KB Output is correct
12 Correct 3 ms 3404 KB Output is correct
13 Correct 3 ms 3404 KB Output is correct
14 Correct 96 ms 16920 KB Output is correct
15 Correct 70 ms 12748 KB Output is correct
16 Correct 131 ms 16676 KB Output is correct
17 Correct 3 ms 3404 KB Output is correct
18 Correct 4 ms 3404 KB Output is correct
19 Correct 3 ms 3404 KB Output is correct
20 Correct 106 ms 17100 KB Output is correct
21 Correct 3 ms 3404 KB Output is correct
22 Correct 3 ms 3404 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3464 KB Output is correct
2 Correct 3 ms 3404 KB Output is correct
3 Correct 3 ms 3404 KB Output is correct
4 Correct 3 ms 3404 KB Output is correct
5 Correct 3 ms 3404 KB Output is correct
6 Correct 3 ms 3404 KB Output is correct
7 Correct 4 ms 3404 KB Output is correct
8 Correct 4 ms 3404 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3404 KB Output is correct
2 Correct 33 ms 6984 KB Output is correct
3 Correct 34 ms 6976 KB Output is correct
4 Correct 48 ms 7796 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3404 KB Output is correct
2 Correct 33 ms 6984 KB Output is correct
3 Correct 34 ms 6976 KB Output is correct
4 Correct 48 ms 7796 KB Output is correct
5 Correct 98 ms 16532 KB Output is correct
6 Correct 105 ms 16176 KB Output is correct
7 Correct 91 ms 16288 KB Output is correct
8 Correct 98 ms 15928 KB Output is correct
9 Correct 54 ms 10276 KB Output is correct
10 Correct 91 ms 14844 KB Output is correct
11 Correct 91 ms 15448 KB Output is correct
12 Correct 64 ms 12072 KB Output is correct
13 Correct 65 ms 12384 KB Output is correct
14 Correct 68 ms 12472 KB Output is correct
15 Correct 69 ms 12580 KB Output is correct
16 Correct 5 ms 3748 KB Output is correct
17 Correct 68 ms 11036 KB Output is correct
18 Correct 79 ms 11932 KB Output is correct
19 Correct 63 ms 11960 KB Output is correct
20 Correct 113 ms 15764 KB Output is correct
21 Correct 89 ms 15440 KB Output is correct
22 Correct 86 ms 15556 KB Output is correct