Submission #766925

#	Time	Username	Problem	Language	Result	Execution time	Memory
766925		birktj	Mechanical Doll (IOI18_doll)	C++14	Compilation error	0 ms	0 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;
      |         ~~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:36:9: error: redeclaration of 'int n'
   36 |     int n = 1;
      |         ^
doll.cpp:25:9: note: 'int n' previously declared here
   25 |     int n = a.size();
      |         ^
doll.cpp:38:14: warning: self-comparison always evaluates to false [-Wtautological-compare]
   38 |     while (n < n) {
      |            ~ ^ ~