oj.uz

Submission #107321

# Submission time Handle Problem Language Result Execution time Memory
107321 2019-04-23T10:27:50 Z PeppaPig Mechanical Doll (IOI18_doll) C++14
6 / 100
 132 ms 16956 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+5;

int n, m, idx;
vector<int> g[N], C, X, Y;

void solve(int u, vector<int> &V) {
    if(V.empty()) return void(C[u] = u);
    if((int)V.size() == 1) return void(C[u] = V[0]);

    int L = 0, sz;
    while((1 << L) < (int)V.size()) ++L;
    sz = 1 << L;

    vector<int> add;
    int now = V.size();
    while((int)V.size() < sz) {
        V.emplace_back(idx-1);
        X.emplace_back(--idx), Y.emplace_back(0);
        add.emplace_back(X.size()-1);
    }
    swap(V[now-1], V[V.size()-1]);

    for(int i = 0; i < sz; i++) {
        int pos = 0;
        for(int j = 0; j < L; j++) pos += (i >> j & 1) << (L - j - 1);
        if(i < pos) swap(V[i], V[pos]);
    }

    for(int len = 2; len <= sz; len <<= 1) {
        int half = len >> 1;
        for(int i = 0; i < sz; i += len) {
            int j = i + half;
            if(j > sz) continue;
            X.emplace_back(V[i]), Y.emplace_back(V[j]);
            V[i] = --idx;
        }
    }
    for(int i : add) Y[i] = V[0];
    C[u] = V[0];
}

void create_circuit(int M, vector<int> A) {
    n = A.size(), m = M;
    C.resize(m + 1);

    for(int i = 0; i < n-1; i++) g[A[i]].emplace_back(A[i+1]);
    g[0].emplace_back(A[0]), g[A[n-1]].emplace_back(0);
    for(int i = 0; i <= m; i++) solve(i, g[i]);

    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4940 KB Output is correct
2 Correct 40 ms 8652 KB Output is correct
3 Correct 38 ms 8268 KB Output is correct
4 Correct 5 ms 4872 KB Output is correct
5 Correct 19 ms 6332 KB Output is correct
6 Correct 58 ms 9980 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4940 KB Output is correct
2 Correct 40 ms 8652 KB Output is correct
3 Correct 38 ms 8268 KB Output is correct
4 Correct 5 ms 4872 KB Output is correct
5 Correct 19 ms 6332 KB Output is correct
6 Correct 58 ms 9980 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct
8 Correct 70 ms 10576 KB Output is correct
9 Correct 69 ms 11008 KB Output is correct
10 Correct 119 ms 13316 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 5 ms 4940 KB Output is correct
13 Correct 6 ms 4900 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4940 KB Output is correct
2 Correct 40 ms 8652 KB Output is correct
3 Correct 38 ms 8268 KB Output is correct
4 Correct 5 ms 4872 KB Output is correct
5 Correct 19 ms 6332 KB Output is correct
6 Correct 58 ms 9980 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct
8 Correct 70 ms 10576 KB Output is correct
9 Correct 69 ms 11008 KB Output is correct
10 Correct 119 ms 13316 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 5 ms 4940 KB Output is correct
13 Correct 6 ms 4900 KB Output is correct
14 Incorrect 132 ms 16956 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -