Submission #782000

#	Time	Username	Problem	Language	Result	Execution time	Memory
782000		faruk	Mechanical Doll (IOI18_doll)	C++17	37 / 100	95 ms	14656 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

void set_idxs(int offset, int curr, int idx, int depth, int &max_node, vector<int> &targets, vector<int> &xs, vector<int> &ys) {
    if (curr >= max_node) {
        int par = (curr - 1) / 2; 
        if (curr % 2)
            xs[par] = targets[idx];
        else
            ys[par] = targets[idx];
        return;
    }
    xs[curr] = -((curr + 1) * 2 - 1) - offset;
    ys[curr] = -((curr + 1) * 2) - offset;
    set_idxs(offset, (curr + 1) * 2 - 1, idx, depth + 1, max_node, targets, xs, ys);
    set_idxs(offset, (curr + 1) * 2, idx + (1 << depth), depth + 1, max_node, targets, xs, ys);
}

pair<vector<int>, vector<int> > getxy(int node, vector<int> targets, int offset) {
    // determine size of last_row
    int siz = 1, needed_nodes = 1;
    while (siz * 2 < targets.size())
        siz *= 2, needed_nodes += siz;
    
    while (targets.size() < 2*siz) {
        targets.push_back(-node);
        swap(targets[targets.size() - 1], targets[targets.size() - 2]);
    }

    vector<int> xs(needed_nodes);
    vector<int> ys(needed_nodes);
    set_idxs(offset, 0, 0, 0, needed_nodes, targets, xs, ys);
    return make_pair(xs, ys);
}

void create_circuit(int M, std::vector<int> A) {
    int N = A.size();
    std::vector<int> C(M + 1);
    std::vector<int> X(M), Y(M);
    C[0] = A[0];
    for (int i = 1; i <= M; ++i)
        C[i] = -i;
    for (int i = 0; i < M; i++)
        X[i] = -(i + 1);

    vector<vector<int> > targets(M + 1);
    for (int i = 0; i < A.size(); i++) {
        int next = i == A.size() - 1 ? 0 : A[i + 1];
        targets[A[i]].push_back(next);
    }

    for (int i = 1; i <= M; i++) {
        if (targets[i].empty())
            continue;
        Y[i - 1] = -(X.size() + 1);
        auto xandy = getxy(i, targets[i], X.size() + 1);
        for (int j = 0; j < xandy.first.size(); j++)
            X.push_back(xandy.first[j]), Y.push_back(xandy.second[j]);
    }

    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > getxy(int, std::vector<int>, int)':
doll.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     while (siz * 2 < targets.size())
      |            ~~~~~~~~^~~~~~~~~~~~~~~~
doll.cpp:27:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |     while (targets.size() < 2*siz) {
      |            ~~~~~~~~~~~~~~~^~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < A.size(); i++) {
      |                     ~~^~~~~~~~~~
doll.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         int next = i == A.size() - 1 ? 0 : A[i + 1];
      |                    ~~^~~~~~~~~~~~~~~
doll.cpp:59:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int j = 0; j < xandy.first.size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~
doll.cpp:39:9: warning: unused variable 'N' [-Wunused-variable]
   39 |     int N = A.size();
      |         ^

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9.0000000018 / 18
• Subtask 6: 28.0000000056 / 56