oj.uz

Submission #766853

# Submission time Handle Problem Language Result Execution time Memory
766853 2023-06-26T08:12:48 Z birktj Mechanical Doll (IOI18_doll) C++14
10 / 100
 1000 ms 13464 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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 633 ms 9168 KB Output is correct
3 Execution timed out 1079 ms 11596 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 633 ms 9168 KB Output is correct
3 Execution timed out 1079 ms 11596 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 633 ms 9168 KB Output is correct
3 Execution timed out 1079 ms 11596 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1075 ms 13464 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 1075 ms 13464 KB Time limit exceeded
3 Halted 0 ms 0 KB -