oj.uz

Submission #756515

# Submission time Handle Problem Language Result Execution time Memory
756515 2023-06-11T18:51:10 Z drdilyor Mechanical Doll (IOI18_doll) C++17
10 / 100
 1000 ms 4920 KB 
#include<bits/stdc++.h>
#include "doll.h"
using namespace std;
using ll = long long;

void create_circuit(int m, std::vector<int> arr) {
    vector<int> c(m+1);
    vector<int> x, y;
    auto add = [&](int a, int b){
        x.push_back(a), y.push_back(b);
        return -(int)x.size();
    };

    auto tree = [&](auto& tree, vector<int> nxt) {
        //cout << "nxt="; for (int i : nxt) cout << (i == INT_MAX ? -1 : i) << ' '; cout << endl;
        if (set<int>(nxt.begin(), nxt.end()).size() == 1) {
            return nxt[0];
        }
        vector<int> odd, even;
        for (int i = 0; i < (int)nxt.size(); i += 2) {
            odd.push_back(nxt[i]);
            even.push_back(nxt[i+1]);
        }
        int t1 = tree(tree, odd);
        int t2 = tree(tree, even);
        return add(t1, t2);
    };


    arr.push_back(0);

    int k = arr.size();
    while (k & (k-1)) k++;
    vector<int> order(k), rev(k);
    for (int i = 0; i < k; i++) {
        for (int j = 0; (1<<j) < k; j++) {
            if (i & (1<<j))
                order[i] |= k >> (j+1);
        }
        rev[order[i]] = i;
    }

    vector<int> brr(k, INT_MAX);

    vector<int> available(order.begin() + k - arr.size(), order.end());
    int cur = 0;
    for (int i = 0; i < k; i++) {
        auto it = find(available.begin(), available.end(), i);
        if (it != available.end())
            brr[*it] = arr[cur++];
    }

    c[0] = tree(tree, brr);

    for (int i = 0; i < (int)x.size(); i++) {
        if (x[i] == INT_MAX)
            x[i] = c[0];
        if (y[i] == INT_MAX)
            y[i] = c[0];
    }
    for (int i = 1; i <= m; i++)
        c[i] = c[0];
    answer(c, x, y);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1086 ms 3360 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1086 ms 3360 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1086 ms 3360 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1090 ms 4920 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1090 ms 4920 KB Time limit exceeded
3 Halted 0 ms 0 KB -