oj.uz

Submission #637188

# Submission time Handle Problem Language Result Execution time Memory
637188 2022-08-31T21:41:12 Z stevancv Mechanical Doll (IOI18_doll) C++14
100 / 100
 170 ms 14344 KB 
#include <bits/stdc++.h>
#include "doll.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 2;
const int mod = 1e9 + 7;
int val[2 * N];
int lc[2 * N], rc[2 * N], root, tsz, bound;
void Create(int &c, int l, int r) {
    if (r < bound) {c = root; return;}
    if (l == r) {c = -val[l]; return;}
    c = ++tsz;
    int mid = l + r >> 1;
    Create(lc[c], l, mid);
    Create(rc[c], mid + 1, r);
}
void create_circuit(int m, vector<int> a) {
    a.push_back(0);
    int n = a.size();
    int x = 1;
    while (x < n) x *= 2;
    vector<int> id(x);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&] (int i, int j) {
        for (int b = 0; b < 20; b++) {
            int p = (1 << b) & i; int q = (1 << b) & j;
            if (p != q) return p < q;
        }
    });
    vector<pair<int, int>> v;
    for (int i = x - n; i < x; i++) v.push_back({id[i], i});
    sort(v.begin(), v.end());
    for (int i = 0; i < n; i++) val[v[i].second] = a[i];
    bound = x - n;
    Create(root, 0, x - 1);
    vector<int> c(m + 1, -1);
    vector<int> X, Y;
    for (int i = 1; i <= tsz; i++) {
        X.push_back(-lc[i]);
        Y.push_back(-rc[i]);
    }
    answer(c, X, Y);
}

Compilation message

doll.cpp: In function 'void Create(int&, int, int)':
doll.cpp:18:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |     int mid = l + r >> 1;
      |               ~~^~~
doll.cpp: In lambda function:
doll.cpp:34:5: warning: control reaches end of non-void function [-Wreturn-type]
   34 |     });
      |     ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 72 ms 5564 KB Output is correct
3 Correct 68 ms 5176 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 10 ms 1492 KB Output is correct
6 Correct 83 ms 7492 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 72 ms 5564 KB Output is correct
3 Correct 68 ms 5176 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 10 ms 1492 KB Output is correct
6 Correct 83 ms 7492 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 140 ms 8884 KB Output is correct
9 Correct 139 ms 10456 KB Output is correct
10 Correct 168 ms 14344 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 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 72 ms 5564 KB Output is correct
3 Correct 68 ms 5176 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 10 ms 1492 KB Output is correct
6 Correct 83 ms 7492 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 140 ms 8884 KB Output is correct
9 Correct 139 ms 10456 KB Output is correct
10 Correct 168 ms 14344 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 163 ms 13832 KB Output is correct
15 Correct 130 ms 9432 KB Output is correct
16 Correct 167 ms 13728 KB Output is correct
17 Correct 0 ms 312 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 170 ms 14088 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 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 1 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 147 ms 8376 KB Output is correct
3 Correct 147 ms 9268 KB Output is correct
4 Correct 156 ms 13468 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 147 ms 8376 KB Output is correct
3 Correct 147 ms 9268 KB Output is correct
4 Correct 156 ms 13468 KB Output is correct
5 Correct 170 ms 13712 KB Output is correct
6 Correct 159 ms 13576 KB Output is correct
7 Correct 164 ms 13572 KB Output is correct
8 Correct 156 ms 13588 KB Output is correct
9 Correct 130 ms 9292 KB Output is correct
10 Correct 158 ms 13596 KB Output is correct
11 Correct 156 ms 13508 KB Output is correct
12 Correct 127 ms 9304 KB Output is correct
13 Correct 150 ms 9428 KB Output is correct
14 Correct 130 ms 9316 KB Output is correct
15 Correct 161 ms 9288 KB Output is correct
16 Correct 3 ms 596 KB Output is correct
17 Correct 84 ms 8660 KB Output is correct
18 Correct 130 ms 9288 KB Output is correct
19 Correct 144 ms 9308 KB Output is correct
20 Correct 165 ms 13576 KB Output is correct
21 Correct 161 ms 13480 KB Output is correct
22 Correct 155 ms 13464 KB Output is correct