oj.uz

Submission #384938

# Submission time Handle Problem Language Result Execution time Memory
384938 2021-04-02T17:14:47 Z arman_ferdous Mechanical Doll (IOI18_doll) C++17
37 / 100
 133 ms 11816 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

#define sz(v) (int)v.size()

const int M = (1 << 20);

int x[M], y[M], cnt[M], maxSwitch;

void build(int u, int L, int R) {
  maxSwitch = max(maxSwitch, u);
  cnt[u] = 0;

  if(L == R) return;
  int mid = L + R >> 1, lc = u << 1, rc = lc | 1;
  x[u] = lc, y[u] = rc;
  build(lc, L, mid); build(rc, mid + 1, R);
}

void insert(int u, int L, int R, int nxt) {
  if(L == R) {
    if(~cnt[u] & 1) x[u] = -nxt;
    else y[u] = -nxt;
    cnt[u] ^= 1;
    return;
  } int mid = L + R >> 1, lc = u << 1, rc = lc | 1;

  if(~cnt[u] & 1) {
    cnt[u] ^= 1;
    insert(lc, L, mid, nxt);
  }
  else {
    cnt[u] ^= 1;
    insert(rc, mid + 1, R, nxt);
  }
}


void create_circuit(int m, vector<int> a) {
  int n = a.size(); 

  while(n + 1 < 2 || __builtin_popcount(n + 1) != 1) {
    a.push_back(-1);
    n++;
  } a.push_back(0); n++;

  build(1, 1, n / 2);
  for(int i : a) insert(1, 1, n / 2, i);

  vector<int> C(m + 1, -1), X, Y;
  X.assign(x + 1, x + 1 + maxSwitch);
  Y.assign(y + 1, y + 1 + maxSwitch);

  for(int &i : X) i = -i;
  for(int &i : Y) i = -i;

  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void build(int, int, int)':
doll.cpp:16:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |   int mid = L + R >> 1, lc = u << 1, rc = lc | 1;
      |             ~~^~~
doll.cpp: In function 'void insert(int, int, int, int)':
doll.cpp:27:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   } int mid = L + R >> 1, lc = u << 1, rc = lc | 1;
      |               ~~^~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Partially correct 94 ms 11072 KB Output is partially correct
3 Partially correct 92 ms 11080 KB Output is partially correct
4 Partially correct 125 ms 11308 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Partially correct 94 ms 11072 KB Output is partially correct
3 Partially correct 92 ms 11080 KB Output is partially correct
4 Partially correct 125 ms 11308 KB Output is partially correct
5 Partially correct 133 ms 11816 KB Output is partially correct
6 Partially correct 112 ms 11632 KB Output is partially correct
7 Partially correct 130 ms 11688 KB Output is partially correct
8 Partially correct 109 ms 11472 KB Output is partially correct
9 Partially correct 123 ms 11000 KB Output is partially correct
10 Partially correct 119 ms 11444 KB Output is partially correct
11 Partially correct 99 ms 11312 KB Output is partially correct
12 Partially correct 90 ms 11004 KB Output is partially correct
13 Partially correct 100 ms 11200 KB Output is partially correct
14 Partially correct 91 ms 11328 KB Output is partially correct
15 Partially correct 94 ms 11412 KB Output is partially correct
16 Partially correct 4 ms 716 KB Output is partially correct
17 Correct 53 ms 6864 KB Output is correct
18 Partially correct 94 ms 11072 KB Output is partially correct
19 Partially correct 117 ms 11072 KB Output is partially correct
20 Partially correct 100 ms 11308 KB Output is partially correct
21 Partially correct 133 ms 11300 KB Output is partially correct
22 Partially correct 98 ms 11316 KB Output is partially correct