oj.uz

Submission #441152

# Submission time Handle Problem Language Result Execution time Memory
441152 2021-07-04T12:28:05 Z prvocislo Mechanical Doll (IOI18_doll) C++17
100 / 100
 424 ms 36080 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

const int maxvr = 6e5 + 100;
//const int maxvr = 100;
vector<int> num(maxvr); // naozajstne cisla vrcholov v strome. Teda switche budu zaporne a prvych m cisel budu v skutocnosti nieco ine
vector<vector<int> > g(maxvr);
int n, m, s, lf, root, first; // mame fiktivny n+1-vy trigger na to aby sme sa vratili do 0
int dfs(int l, int r)
{
  if (r < first) return root;
  if (l == r) return lf++;
  int now = s;
  s++;
  g[now].push_back(dfs(l, (l+r)/2));
  g[now].push_back(dfs((l+r)/2+1, r));
  return now;
}
vector<int> stav(maxvr, 0);
int get_next() // ideme na nasledujuci vrchol ktory ma cislo mensie ako n
{
  int vr = root;
  while (vr >= n)
  {
    int nw = g[vr][stav[vr]];
    stav[vr] ^= 1;
    vr = nw;
  }
  return vr;
}
void create_circuit(int M, vector<int> a) {
  m = M;
  a.push_back(0), n = a.size();
  lf = 0, s = n;
  int n2 = 1;
  while (n2 < n) n2 <<= 1;
  root = n, first = n2 - n; dfs(0, n2 - 1);
  for (int i = 0; i < n; i++)
  {
    int vr = get_next();
    num[vr] = a[i];
  }
  for (int i = n; i < s; i++)
  {
    num[i] = -(i - (n-1));
  }
  vector<int> c(m+1, num[root]), x(s-n), y(s-n);
  for (int i = n; i < s; i++)
  {
    x[i-n] = num[g[i][0]];
    y[i-n] = num[g[i][1]];
  }
  /*for (int i = 0; i <= m; i++) cout << i << " " << c[i] << endl;
  for (int i = 0; i < x.size(); i++)
  {
    cout << -(i+1) << " " << x[i] << endl;
    cout << -(i+1) << " " << y[i] << endl;
  }*/
  answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19020 KB Output is correct
2 Correct 111 ms 24384 KB Output is correct
3 Correct 84 ms 24724 KB Output is correct
4 Correct 11 ms 19000 KB Output is correct
5 Correct 22 ms 20172 KB Output is correct
6 Correct 180 ms 27660 KB Output is correct
7 Correct 11 ms 19020 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19020 KB Output is correct
2 Correct 111 ms 24384 KB Output is correct
3 Correct 84 ms 24724 KB Output is correct
4 Correct 11 ms 19000 KB Output is correct
5 Correct 22 ms 20172 KB Output is correct
6 Correct 180 ms 27660 KB Output is correct
7 Correct 11 ms 19020 KB Output is correct
8 Correct 209 ms 29328 KB Output is correct
9 Correct 226 ms 29844 KB Output is correct
10 Correct 375 ms 34960 KB Output is correct
11 Correct 11 ms 19020 KB Output is correct
12 Correct 11 ms 19020 KB Output is correct
13 Correct 11 ms 19064 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19020 KB Output is correct
2 Correct 111 ms 24384 KB Output is correct
3 Correct 84 ms 24724 KB Output is correct
4 Correct 11 ms 19000 KB Output is correct
5 Correct 22 ms 20172 KB Output is correct
6 Correct 180 ms 27660 KB Output is correct
7 Correct 11 ms 19020 KB Output is correct
8 Correct 209 ms 29328 KB Output is correct
9 Correct 226 ms 29844 KB Output is correct
10 Correct 375 ms 34960 KB Output is correct
11 Correct 11 ms 19020 KB Output is correct
12 Correct 11 ms 19020 KB Output is correct
13 Correct 11 ms 19064 KB Output is correct
14 Correct 407 ms 35920 KB Output is correct
15 Correct 209 ms 29888 KB Output is correct
16 Correct 352 ms 35664 KB Output is correct
17 Correct 11 ms 19020 KB Output is correct
18 Correct 12 ms 19020 KB Output is correct
19 Correct 12 ms 19112 KB Output is correct
20 Correct 424 ms 36080 KB Output is correct
21 Correct 11 ms 19104 KB Output is correct
22 Correct 11 ms 19104 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 18988 KB Output is correct
2 Correct 11 ms 19000 KB Output is correct
3 Correct 11 ms 19036 KB Output is correct
4 Correct 13 ms 19080 KB Output is correct
5 Correct 11 ms 19020 KB Output is correct
6 Correct 11 ms 19020 KB Output is correct
7 Correct 11 ms 19064 KB Output is correct
8 Correct 11 ms 19020 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19020 KB Output is correct
2 Correct 192 ms 27920 KB Output is correct
3 Correct 230 ms 27892 KB Output is correct
4 Correct 355 ms 32772 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19020 KB Output is correct
2 Correct 192 ms 27920 KB Output is correct
3 Correct 230 ms 27892 KB Output is correct
4 Correct 355 ms 32772 KB Output is correct
5 Correct 378 ms 35400 KB Output is correct
6 Correct 401 ms 35188 KB Output is correct
7 Correct 349 ms 35232 KB Output is correct
8 Correct 350 ms 34848 KB Output is correct
9 Correct 226 ms 28820 KB Output is correct
10 Correct 415 ms 34900 KB Output is correct
11 Correct 353 ms 34464 KB Output is correct
12 Correct 192 ms 29156 KB Output is correct
13 Correct 193 ms 29588 KB Output is correct
14 Correct 233 ms 29632 KB Output is correct
15 Correct 185 ms 29768 KB Output is correct
16 Correct 14 ms 19404 KB Output is correct
17 Correct 227 ms 29180 KB Output is correct
18 Correct 230 ms 29244 KB Output is correct
19 Correct 190 ms 29056 KB Output is correct
20 Correct 402 ms 34764 KB Output is correct
21 Correct 358 ms 34428 KB Output is correct
22 Correct 417 ms 34516 KB Output is correct