oj.uz

Submission #1092952

# Submission time Handle Problem Language Result Execution time Memory
1092952 2024-09-25T13:43:54 Z belgianbot Mechanical Doll (IOI18_doll) C++17
100 / 100
 98 ms 23588 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define pb push_back
#define fi first 
#define se second
#define size(x) (int)(x.size())

using namespace std;

vector<vector<int>> adj;
vector<int> C, X, Y;

int cnt = -1;

void divide(vector<int> *a) {
    if (size((*a)) == 2) {
        X.pb((*a)[0]);
        Y.pb((*a)[1]);
        return;
    }

    vector<int> b, c;
    for (int i = 0; i < size((*a)); i++) {
        if (i & 1) c.pb( (*a)[i]);
        else b.pb((*a)[i]);
    }
    X.pb(cnt); cnt--; Y.pb(0); int n = size(Y);
    divide(&b);
    Y[n - 1] = cnt; cnt--;
    divide(&c);
}
void create_circuit(int M, vector<int> A) {

    C.resize(M + 1);
    int N = size(A);
    int fact = 1, i = 0, last = 0;
    vector<vector<int>> div;
    div.push_back(A);
    while (fact <= N) {
        cnt--;
        Y.push_back(last);
        last = -size(Y);
        if (N & (1 << i)) {
            vector<vector<int>> newDiv;
            vector<int> vec;
            for (auto x : div) {
                newDiv.push_back(vector<int>(x.begin(), x.begin() + size(x) / 2));
                newDiv.push_back(vector<int>(x.begin() + size(x) / 2 + 1, x.end()));
                vec.push_back(x[size(x) / 2]);
            }
            swap(div, newDiv);
            if (i) {
                X.push_back(cnt);
                cnt--;
                divide(&vec);
            }
            else X.push_back(vec[0]);

        }
        else {
            X.push_back(0);
            vector<vector<int>> newDiv;
            for (auto x : div) {
                newDiv.push_back(vector<int>(x.begin(), x.begin() + size(x) / 2));
                newDiv.push_back(vector<int>(x.begin() + size(x) / 2, x.end()));
            }
            swap(div, newDiv);
        }
        
        fact <<= 1;
        i++;
    }
    for (int i = 0; i <= M; i++) C[i] = last;
    for (int& x: X) if (!x) x = last;
    answer(C, X, Y);

}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 33 ms 10556 KB Output is correct
3 Correct 32 ms 10540 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1744 KB Output is correct
6 Correct 44 ms 12204 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 33 ms 10556 KB Output is correct
3 Correct 32 ms 10540 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1744 KB Output is correct
6 Correct 44 ms 12204 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 61 ms 20268 KB Output is correct
9 Correct 64 ms 20520 KB Output is correct
10 Correct 82 ms 23568 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 33 ms 10556 KB Output is correct
3 Correct 32 ms 10540 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1744 KB Output is correct
6 Correct 44 ms 12204 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 61 ms 20268 KB Output is correct
9 Correct 64 ms 20520 KB Output is correct
10 Correct 82 ms 23568 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 98 ms 23564 KB Output is correct
15 Correct 59 ms 20208 KB Output is correct
16 Correct 79 ms 23320 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 83 ms 23588 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 63 ms 19876 KB Output is correct
3 Correct 60 ms 20016 KB Output is correct
4 Correct 74 ms 23312 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 63 ms 19876 KB Output is correct
3 Correct 60 ms 20016 KB Output is correct
4 Correct 74 ms 23312 KB Output is correct
5 Correct 78 ms 23316 KB Output is correct
6 Correct 77 ms 23292 KB Output is correct
7 Correct 79 ms 23320 KB Output is correct
8 Correct 83 ms 23316 KB Output is correct
9 Correct 54 ms 20280 KB Output is correct
10 Correct 71 ms 23284 KB Output is correct
11 Correct 77 ms 23156 KB Output is correct
12 Correct 56 ms 20264 KB Output is correct
13 Correct 67 ms 20172 KB Output is correct
14 Correct 57 ms 20008 KB Output is correct
15 Correct 61 ms 20112 KB Output is correct
16 Correct 4 ms 1008 KB Output is correct
17 Correct 45 ms 12348 KB Output is correct
18 Correct 55 ms 20016 KB Output is correct
19 Correct 57 ms 20012 KB Output is correct
20 Correct 83 ms 23312 KB Output is correct
21 Correct 74 ms 23332 KB Output is correct
22 Correct 75 ms 23240 KB Output is correct