oj.uz

Submission #604965

# Submission time Handle Problem Language Result Execution time Memory
604965 2022-07-25T11:27:35 Z yuto1115 Mechanical Doll (IOI18_doll) C++17
100 / 100
 92 ms 9520 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for (ll i = ll(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

void create_circuit(int m, vi a) {
    int n = SZ(a);
    vi c(m + 1, -1), x, y;
    int _n = 1;
    while (_n <= n) _n *= 2;
    vi ls;
    auto f = [&](auto &f, int l, int r, int id, int d) -> int {
        if (r + n + 1 <= _n) return -1;
        if (r - l == 1) {
            ls.pb(id);
            return id;
        }
        int now = SZ(x);
        x.pb(0), y.pb(0);
        x[now] = f(f, l, (l + r) / 2, id, d + 1);
        y[now] = f(f, (l + r) / 2, r, id + (1 << d), d + 1);
        return -(now + 1);
    };
    f(f, 0, _n, 0, 0);
    sort(all(ls));
    assert(SZ(ls) == n + 1);
    assert(ls.back() == _n - 1);
    vi rev(_n);
    rep(i, n + 1) rev[ls[i]] = (i == n ? 0 : a[i]);
    for (int &i: x) if (i >= 0) i = rev[i];
    for (int &i: y) if (i >= 0) i = rev[i];
    answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 31 ms 4312 KB Output is correct
3 Correct 36 ms 3880 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 43 ms 5544 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 31 ms 4312 KB Output is correct
3 Correct 36 ms 3880 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 43 ms 5544 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 50 ms 6684 KB Output is correct
9 Correct 60 ms 7116 KB Output is correct
10 Correct 84 ms 9520 KB Output is correct
11 Correct 0 ms 280 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 31 ms 4312 KB Output is correct
3 Correct 36 ms 3880 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 43 ms 5544 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 50 ms 6684 KB Output is correct
9 Correct 60 ms 7116 KB Output is correct
10 Correct 84 ms 9520 KB Output is correct
11 Correct 0 ms 280 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 80 ms 9096 KB Output is correct
15 Correct 67 ms 6292 KB Output is correct
16 Correct 77 ms 8900 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 92 ms 9272 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 48 ms 5956 KB Output is correct
3 Correct 44 ms 5948 KB Output is correct
4 Correct 77 ms 8464 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 48 ms 5956 KB Output is correct
3 Correct 44 ms 5948 KB Output is correct
4 Correct 77 ms 8464 KB Output is correct
5 Correct 85 ms 8872 KB Output is correct
6 Correct 80 ms 8660 KB Output is correct
7 Correct 78 ms 8692 KB Output is correct
8 Correct 77 ms 8676 KB Output is correct
9 Correct 53 ms 5848 KB Output is correct
10 Correct 88 ms 8616 KB Output is correct
11 Correct 82 ms 8496 KB Output is correct
12 Correct 46 ms 5944 KB Output is correct
13 Correct 46 ms 6032 KB Output is correct
14 Correct 47 ms 6192 KB Output is correct
15 Correct 50 ms 6196 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 47 ms 5568 KB Output is correct
18 Correct 50 ms 5940 KB Output is correct
19 Correct 47 ms 5852 KB Output is correct
20 Correct 73 ms 8732 KB Output is correct
21 Correct 77 ms 8464 KB Output is correct
22 Correct 75 ms 8468 KB Output is correct