제출 #969902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969902		BestCrazyNoob	자동 인형 (IOI18_doll)	C++17	85.55 / 100	227 ms	18632 KiB

doll

#include "doll.h"
#include <vector>
#include <array>
#include <algorithm>

using namespace std;
constexpr int H = 19;

vector<vector<int>> graph;
vector<int> C, X, Y;
int nxt = -1;
array<vector<int>, H> pos;

void create(int curr, int sz, vector<int> v, int root, int h) {
    // For local vectors
    curr = -1-curr;

    if (sz == 2) {
        X[curr] = v.size() > 1 ? v[0] : root;
        Y[curr] = v.size() > 1 ? v[1] : v[0];
    } else {
        if (v.size() > sz/2) {
            X[curr] = nxt--;
            Y[curr] = nxt--;
            vector<int> i1(pos[h].end() - v.size(), pos[h].begin() + sz/2), i2(pos[h].begin() + sz/2, pos[h].end()), v1, v2;
            sort(i1.begin(), i1.end());
            sort(i2.begin(), i2.end());
            int i = 0, j = 0, x = 0;
            while (i < v1.size() || j < i2.size()) {
                if (i < i1.size() && (j == i2.size() || i1[i] < i2[j])) {
                    i1[i++] = x++;
                } else {
                    i2[j++] = x++;
                }
            }
            for (int i: i1) v1.push_back(v[i]);
            for (int i: i2) v2.push_back(v[i]);
            create(X[curr], sz/2, v1, root, h-1);
            create(Y[curr], sz/2, v2, root, h-1);
        } else {
            X[curr] = root;
            Y[curr] = nxt--;
            create(Y[curr], sz/2, v, root, h-1);
        }
    }
}

void calc_recur(vector<int> v, int h, int i) {
    if (v.size() == 1) {
        pos[h][i] = v[0];
        return;
    }
    vector<int> v1, v2;
    for (int i = 0; i < v.size(); i++) {
        if (i % 2 == 0) v1.push_back(v[i]);
        else v2.push_back(v[i]);
    }
    calc_recur(v1, h, i);
    calc_recur(v2, h, i + v2.size());
}

void create_circuit(int M, vector<int> A) {
    // SETUP
    for (int h = 0; h < H; h++) {
        pos[h].resize(1 << h);
        vector<int> v;
        v.resize(1 << h);
        for (int i = 0; i < (1 << h); i++) v[i] = i;
        calc_recur(v, h, 0);
    }
    
    const int N = A.size();
    graph.resize(M+1);
    int last = 0;
    for (int i = 0; i < N; i++) {
        graph[last].push_back(A[i]);
        last = A[i];
    }
    graph[last].push_back(0);

    C.resize(M+1);
    X.resize(400'000);
    Y.resize(400'000);
    for (int i = 0; i < M+1; i++) {
        if (graph[i].size() == 0) {
            C[i] = 0;
        } else if (graph[i].size() == 1) {
            C[i] = graph[i][0];
        } else {
            int sz = 1, h = 0;
            while (sz < graph[i].size()) {
                h++;
                sz *= 2;
            }
            C[i] = nxt--;
            create(C[i], sz, graph[i], C[i], h);
        }
    }
    X.resize(-1-nxt);
    Y.resize(-1-nxt);
    answer(C, X, Y);
}

컴파일 시 표준 에러 (stderr) 메시지

doll.cpp: In function 'void create(int, int, std::vector<int>, int, int)':
doll.cpp:22:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |         if (v.size() > sz/2) {
      |             ~~~~~~~~~^~~~~~
doll.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |             while (i < v1.size() || j < i2.size()) {
      |                    ~~^~~~~~~~~~~
doll.cpp:29:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |             while (i < v1.size() || j < i2.size()) {
      |                                     ~~^~~~~~~~~~~
doll.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |                 if (i < i1.size() && (j == i2.size() || i1[i] < i2[j])) {
      |                     ~~^~~~~~~~~~~
doll.cpp:30:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |                 if (i < i1.size() && (j == i2.size() || i1[i] < i2[j])) {
      |                                       ~~^~~~~~~~~~~~
doll.cpp: In function 'void calc_recur(std::vector<int>, int, int)':
doll.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             while (sz < graph[i].size()) {
      |                    ~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 41.5530038336 / 56