oj.uz

Submission #300275

# Submission time Handle Problem Language Result Execution time Memory
300275 2020-09-17T03:51:03 Z MickyOr Mechanical Doll (IOI18_doll) C++17
100 / 100
 690 ms 60636 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define fore(i, b, e) for (int i = b; i < (int)e; ++i)
#define pb push_back

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;

vector<vi> G;
vi leafs;
map<int, int> leafNo;

void genGraph(int lvl, int maxLvl) {
  if (lvl == maxLvl) return;
  G.pb(vi());
  int v = G.size()-1;
  if (lvl+1 != maxLvl) {
    // X
    G[v].pb(G.size());
    genGraph(lvl+1, maxLvl);
    // Y
    G[v].pb(G.size());
    genGraph(lvl+1, maxLvl);    
  }
  else {
    leafs.pb(v);
  }
}

vi order;

void genOrder(vi &vals) {
  if (vals.size() == 1) {
    order.pb(vals.back());
    return;
  }
  vi L, R;
  fore(i, 0, vals.size()) {
    if (i&1) R.pb( vals[i] );
    else L.pb( vals[i] );
  }
  genOrder(L);
  genOrder(R);
}

vector<bool> isActive;

void delSwitches(int v) {
  if (G[v].size() == 0) {
    return;
  }
  delSwitches(G[v][0]);
  delSwitches(G[v][1]);
  if (isActive[G[v][0]] || isActive[G[v][1]]) isActive[v] = true;
  else isActive[v] = false;
}

map<int, ii> switchDirs;

void genAnswer(int v, int curS, int &S) {
  if (!isActive[v] || G[v].size() == 0) return;
  int L = G[v][0];
  int R = G[v][1];
  int xS = -1, yS = -1;
  if (!isActive[L]) {
    xS = -1;
  }
  else {
    if (leafNo.count(L)) xS = leafNo[L];
    else xS = --S;
  }
  if (leafNo.count(R)) yS = leafNo[R];
  else yS = --S;
  switchDirs[curS] = {xS, yS};
  genAnswer(L, xS, S);
  genAnswer(R, yS, S);
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  std::vector<int> C;
  std::vector<int> X, Y;
  if (N == 1) {
    C.pb(A[0]);
    fore(i, 0, M) C.pb(0);
    answer(C, X, Y);
    return;
  }
  A.pb(0);
  N++;
  int pot = 0, base = 1;
  while (base < N) {
    base <<= 1;
    pot++;
  }
  
  genGraph(0, pot+1); // las hojas son los cuadrados
  
  vi vals;
  fore(i, 0, base) vals.pb(i);
  genOrder(vals);
  vi nxt(base, -1), invP(base);
  fore(i, 0, base) {
    invP[order[i]] = i;
    leafNo[leafs[i]] = order[i];
  }
  for (int i = base-2; i >= 0; i--) {
    nxt[i] = invP[i+1];
  }

  isActive.assign(G.size(), false);
  for (int i = base-1, j = 0; j < N; j++, i--) {
    isActive[leafs[i]] = true;
  }

  delSwitches(0);
  int accDel = 0;
  fore(i, 0, base) {
    int leaf = leafs[invP[i]];
    if (!isActive[leaf]) accDel++;
    else leafNo[leaf] = A[ leafNo[leaf] - accDel ];
  }

  fore(i, 0, M+1) C.pb(-1);
  int S = -1;
  genAnswer(0, -1, S);
  for (int i = -1; i >= S; --i) {
    assert( switchDirs.count(i) == 1 );
    X.pb(switchDirs[i].first);
    Y.pb(switchDirs[i].second);
  }

  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 196 ms 27808 KB Output is correct
3 Correct 194 ms 27248 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 13 ms 1604 KB Output is correct
6 Correct 237 ms 31584 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 196 ms 27808 KB Output is correct
3 Correct 194 ms 27248 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 13 ms 1604 KB Output is correct
6 Correct 237 ms 31584 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 403 ms 52880 KB Output is correct
9 Correct 447 ms 53556 KB Output is correct
10 Correct 588 ms 60636 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 196 ms 27808 KB Output is correct
3 Correct 194 ms 27248 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 13 ms 1604 KB Output is correct
6 Correct 237 ms 31584 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 403 ms 52880 KB Output is correct
9 Correct 447 ms 53556 KB Output is correct
10 Correct 588 ms 60636 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 690 ms 60224 KB Output is correct
15 Correct 450 ms 52504 KB Output is correct
16 Correct 658 ms 59896 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 523 ms 60384 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 2 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 2 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 433 ms 51668 KB Output is correct
3 Correct 416 ms 51604 KB Output is correct
4 Correct 607 ms 58840 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 433 ms 51668 KB Output is correct
3 Correct 416 ms 51604 KB Output is correct
4 Correct 607 ms 58840 KB Output is correct
5 Correct 655 ms 59848 KB Output is correct
6 Correct 562 ms 59644 KB Output is correct
7 Correct 574 ms 59732 KB Output is correct
8 Correct 681 ms 59504 KB Output is correct
9 Correct 460 ms 51608 KB Output is correct
10 Correct 532 ms 59380 KB Output is correct
11 Correct 580 ms 59140 KB Output is correct
12 Correct 381 ms 51876 KB Output is correct
13 Correct 452 ms 52116 KB Output is correct
14 Correct 424 ms 52184 KB Output is correct
15 Correct 446 ms 52224 KB Output is correct
16 Correct 10 ms 1928 KB Output is correct
17 Correct 327 ms 32880 KB Output is correct
18 Correct 434 ms 51792 KB Output is correct
19 Correct 435 ms 51868 KB Output is correct
20 Correct 614 ms 59364 KB Output is correct
21 Correct 568 ms 59024 KB Output is correct
22 Correct 597 ms 59156 KB Output is correct