oj.uz

Submission #766926

# Submission time Handle Problem Language Result Execution time Memory
766926 2023-06-26T09:04:46 Z birktj Mechanical Doll (IOI18_doll) C++14
100 / 100
 72 ms 13860 KB 
#include "doll.h"
#include <iostream>
#include <algorithm>

using namespace std;

bool used[400000];
int map[400000];

void print_tree(int i, int indent, vector<int> &X, vector<int> &Y) {
    if (i >= X.size()) return;
    cerr << string(indent*2, ' ') << -i <<  ": x = " << X[i-1] << " y = " << Y[i-1] << " used = " << used[i-1] << endl;
    print_tree(i*2, indent+1, X, Y);
    print_tree(i*2+1, indent+1, X, Y);
}

int get_num(int i, int d, int acc) {
    if (d == 0) return acc;
    return get_num(i / 2, d-1, acc*2 + i%2);
}

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

    A.push_back(0);
    A.erase(A.begin());

    int N = 1;
    int d = 0;
    while (N < n) {
        N *= 2;
        d++;
    }
    int skip = N - n;
    vector<int> X(N, -1), Y(N, -1);
    
    for (int i = 1; i < N/2; i++) {
        X[i-1] = -i*2;
        Y[i-1] = -i*2 - 1;
    }

    vector<pair<int, int>> order;

    for (int i = skip; i < N; i++) {
        used[N/2 - 1 + i/2] = true;
        order.push_back({get_num(i, d, 0), i});
    }

    sort(order.begin(), order.end());

    for (int i = skip; i < N; i++) {
        int j = order[i - skip].second;
        int path = A[i - skip];

        if (j % 2 == 0)
            X[N/2 - 1 + j/2] = path;
        else
            Y[N/2 - 1 + j/2] = path;
    }

    for (int i = N/2-1; i > 0; i--)
        used[i-1] = used[i*2-1] || used[i*2];

    int map_count = 0;
    for (int i = 0; i < N; i++) {
        if (used[i]) {
            map[i] = -map_count-1;
            map_count++;
        }
        else {
            map[i] = -1;
        }
    }

    vector<int> X2(map_count), Y2(map_count);

    int mapi = 0;
    for (int i = 0; i < N; i++) {
        if (used[i]) {
            X2[mapi] = X[i] < 0 ? map[-X[i]-1] : X[i];
            Y2[mapi] = Y[i] < 0 ? map[-Y[i]-1] : Y[i];
            mapi++;
        }
    }

    //print_tree(1, 0, X, Y);

    answer(C, X2, Y2);
}

Compilation message

doll.cpp: In function 'void print_tree(int, int, std::vector<int>&, std::vector<int>&)':
doll.cpp:11:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     if (i >= X.size()) return;
      |         ~~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 27 ms 4820 KB Output is correct
3 Correct 25 ms 5328 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 39 ms 7064 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 27 ms 4820 KB Output is correct
3 Correct 25 ms 5328 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 39 ms 7064 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 44 ms 7984 KB Output is correct
9 Correct 47 ms 9800 KB Output is correct
10 Correct 72 ms 12600 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 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 27 ms 4820 KB Output is correct
3 Correct 25 ms 5328 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 39 ms 7064 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 44 ms 7984 KB Output is correct
9 Correct 47 ms 9800 KB Output is correct
10 Correct 72 ms 12600 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 71 ms 12160 KB Output is correct
15 Correct 49 ms 10076 KB Output is correct
16 Correct 71 ms 13408 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 72 ms 13860 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 0 ms 212 KB Output is correct
2 Correct 0 ms 308 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 1 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 41 ms 7124 KB Output is correct
3 Correct 39 ms 8656 KB Output is correct
4 Correct 68 ms 12960 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 41 ms 7124 KB Output is correct
3 Correct 39 ms 8656 KB Output is correct
4 Correct 68 ms 12960 KB Output is correct
5 Correct 69 ms 13356 KB Output is correct
6 Correct 72 ms 13080 KB Output is correct
7 Correct 70 ms 13240 KB Output is correct
8 Correct 67 ms 13008 KB Output is correct
9 Correct 40 ms 9672 KB Output is correct
10 Correct 67 ms 12964 KB Output is correct
11 Correct 65 ms 12836 KB Output is correct
12 Correct 44 ms 9640 KB Output is correct
13 Correct 42 ms 8260 KB Output is correct
14 Correct 43 ms 9804 KB Output is correct
15 Correct 43 ms 9924 KB Output is correct
16 Correct 2 ms 576 KB Output is correct
17 Correct 45 ms 8016 KB Output is correct
18 Correct 40 ms 8020 KB Output is correct
19 Correct 40 ms 9680 KB Output is correct
20 Correct 66 ms 12856 KB Output is correct
21 Correct 65 ms 12820 KB Output is correct
22 Correct 68 ms 12844 KB Output is correct