Submission #766926

#	Time	Username	Problem	Language	Result	Execution time	Memory
766926		birktj	자동 인형 (IOI18_doll)	C++14	100 / 100	72 ms	13860 KiB

doll

#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 (stderr)

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56