oj.uz

Submission #465000

# Submission time Handle Problem Language Result Execution time Memory
465000 2021-08-14T20:18:00 Z blue Mechanical Doll (IOI18_doll) C++17
100 / 100
 266 ms 11752 KB 
#include "doll.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;

int N;
int k;

const int rt = 1e9;

vector<int> I;

void create_circuit(int M, vector<int> A)
{
    N = A.size();
    // if(A.size() == 1)
    // {
    //     vector<int> C(M+1, 0);
    //     C[0] = A[0];
    //     vector<int> X(0), Y(0);
    //     answer(C, X, Y);
    //     return;
    // }

    for(k = 0; (1 << k) < N; k++);

    I = vector<int>( (1 << k) );
    for(int i = 0; i < (1 << k); i++)
        I[i] = i;

    sort(I.begin(), I.end(), [] (int p, int q)
    {
        for(int y = 0; y < k; y++)
        {
            if((p & (1 << y)) < (q & (1 << y)))
                return 1;
            else if((q & (1 << y)) < (p & (1 << y)))
                return 0;
        }
        return 0;
    });

    vector<int> J(N);
    for(int i = 0; i < N; i++) J[i] = I.size() - N + i;
    sort(J.begin(), J.end(), [] (int x, int y)
    {
        return I[x] < I[y];
    });

    vector<int> A1[k+1];

    A1[k] = vector<int>((1 << k), rt);

    for(int i = 1; i < N; i++)
        A1[k][ J[i-1] ] = A[i];

    A1[k][J[N-1]] = 0;


    int S = 0;
    vector<int> C(M+1);
    vector<int> X;
    vector<int> Y;
    for(int l = k-1; l >= 0; l--)
    {
        for(int i = 0; i < (1 << l); i++)
        {
            if(A1[l+1][2*i] == A1[l+1][2*i+1])
                A1[l].push_back(A1[l+1][2*i]);
            else
            {
                S++;
                A1[l].push_back(-S);
                X.push_back(A1[l+1][2*i]);
                Y.push_back(A1[l+1][2*i+1]);
            }
        }
    }
    C[0] = A[0];
    for(int i = 1; i <= M; i++)
        C[i] = -S;

    for(int j = 1; j <= S; j++)
    {
        if(X[j-1] == rt)
            X[j-1] = -S;
        if(Y[j-1] == rt)
            Y[j-1] = -S;
    }

    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 70 ms 4784 KB Output is correct
3 Correct 93 ms 5020 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 116 ms 6568 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 70 ms 4784 KB Output is correct
3 Correct 93 ms 5020 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 116 ms 6568 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 123 ms 7500 KB Output is correct
9 Correct 197 ms 9420 KB Output is correct
10 Correct 237 ms 11752 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 70 ms 4784 KB Output is correct
3 Correct 93 ms 5020 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 116 ms 6568 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 123 ms 7500 KB Output is correct
9 Correct 197 ms 9420 KB Output is correct
10 Correct 237 ms 11752 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 241 ms 11396 KB Output is correct
15 Correct 194 ms 8920 KB Output is correct
16 Correct 229 ms 11180 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 232 ms 11576 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 1 ms 296 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 91 ms 3504 KB Output is correct
3 Correct 161 ms 5024 KB Output is correct
4 Correct 177 ms 5816 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 91 ms 3504 KB Output is correct
3 Correct 161 ms 5024 KB Output is correct
4 Correct 177 ms 5816 KB Output is correct
5 Correct 228 ms 10956 KB Output is correct
6 Correct 229 ms 10712 KB Output is correct
7 Correct 228 ms 10816 KB Output is correct
8 Correct 224 ms 10584 KB Output is correct
9 Correct 177 ms 7460 KB Output is correct
10 Correct 266 ms 10560 KB Output is correct
11 Correct 220 ms 10492 KB Output is correct
12 Correct 191 ms 8092 KB Output is correct
13 Correct 117 ms 6680 KB Output is correct
14 Correct 223 ms 8760 KB Output is correct
15 Correct 190 ms 8760 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 118 ms 6568 KB Output is correct
18 Correct 118 ms 6568 KB Output is correct
19 Correct 187 ms 8188 KB Output is correct
20 Correct 235 ms 10576 KB Output is correct
21 Correct 222 ms 10652 KB Output is correct
22 Correct 225 ms 10580 KB Output is correct