oj.uz

Submission #713823

# Submission time Handle Problem Language Result Execution time Memory
713823 2023-03-23T05:49:27 Z PixelCat Mechanical Doll (IOI18_doll) C++14
100 / 100
 83 ms 9888 KB 
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "doll.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXM = 100010;

vector<int> x, y;

int solve(vector<int> &v, int l, int r, int n) {
    if(r < n) return -1;
    if(l == r) return v[l];
    int m = (l + r) / 2;
    int id = sz(x);
    x.eb(0); y.eb(0);
    // int a = solve(v, m + 1, r, n);
    int a = solve(v, l, m, n);
    // int b = solve(v, l, m, n);
    int b = solve(v, m + 1, r, n);
    x[id] = a; y[id] = b;
    // cout << l << " " << r << " " << id << " " << x[id] << " " << y[id] << " " << (-(id + 1)) << "\n" << flush;
    return -(id + 1);
}

void rev(int n, vector<int> &v) {
    int j = 0;
    For(i, 0, n - 1) {
        if(i < j) swap(v[i], v[j]);
        for(int k = n >> 1; (j ^= k) < k; k >>= 1);
    }
}

void create_circuit(int M, std::vector<int> A) {
    // if(M == 1) {
    //     solve2(sz(A));
    //     return;
    // }
    int lgn = __lg(sz(A) - 1) + 1;
    int n = (1 << lgn);

    A.eb(0);
    vector<int> ans(M + 1, -1);
    reverse(all(A));
    ans[0] = A.back();
    A.pop_back();

    vector<int> b(n);
    For(i, 0, n - 1) b[i] = i;
    rev(n, b);
    b.erase(b.begin() + sz(A), b.end());
    sort(all(b));
    vector<int> c(n, -1);
    For(i, 0, sz(A) - 1) {
        c[b[i]] = A[i];
    }
    rev(n, c);
    reverse(all(c));

    solve(c, 0, n - 1, n - sz(A));
    answer(ans, x, y);
}


/*

4 16
1 2 1 3 1 3 1 1 2 1 3 1 3 1 4 4

1 13
1 1 1 1 1 1 1 1 1 1 1 1 1

*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 30 ms 4148 KB Output is correct
3 Correct 29 ms 4408 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 43 ms 5820 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 1 ms 212 KB Output is correct
2 Correct 30 ms 4148 KB Output is correct
3 Correct 29 ms 4408 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 43 ms 5820 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 53 ms 7588 KB Output is correct
9 Correct 55 ms 7548 KB Output is correct
10 Correct 81 ms 9888 KB Output is correct
11 Correct 0 ms 212 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 1 ms 212 KB Output is correct
2 Correct 30 ms 4148 KB Output is correct
3 Correct 29 ms 4408 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 43 ms 5820 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 53 ms 7588 KB Output is correct
9 Correct 55 ms 7548 KB Output is correct
10 Correct 81 ms 9888 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 79 ms 9396 KB Output is correct
15 Correct 58 ms 6784 KB Output is correct
16 Correct 81 ms 9176 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 83 ms 9592 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 224 KB Output is correct
6 Correct 1 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 45 ms 6448 KB Output is correct
3 Correct 47 ms 6384 KB Output is correct
4 Correct 70 ms 8620 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 45 ms 6448 KB Output is correct
3 Correct 47 ms 6384 KB Output is correct
4 Correct 70 ms 8620 KB Output is correct
5 Correct 78 ms 9000 KB Output is correct
6 Correct 75 ms 8804 KB Output is correct
7 Correct 75 ms 8900 KB Output is correct
8 Correct 73 ms 8704 KB Output is correct
9 Correct 44 ms 6376 KB Output is correct
10 Correct 75 ms 8688 KB Output is correct
11 Correct 76 ms 8608 KB Output is correct
12 Correct 49 ms 6388 KB Output is correct
13 Correct 46 ms 6888 KB Output is correct
14 Correct 50 ms 6584 KB Output is correct
15 Correct 49 ms 6732 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 45 ms 6700 KB Output is correct
18 Correct 44 ms 6592 KB Output is correct
19 Correct 47 ms 6384 KB Output is correct
20 Correct 72 ms 8552 KB Output is correct
21 Correct 71 ms 8508 KB Output is correct
22 Correct 71 ms 8624 KB Output is correct