제출 #1068442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1068442		TheQuantiX	자동 인형 (IOI18_doll)	C++17	37 / 100	117 ms	9284 KiB

doll

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

using namespace std;
using ll = long long;

constexpr ll INF = 1000000000;

ll nxt = -2;

void connect(ll x, vector<int> &X, vector<int> &Y, ll idx) {
    // cout << x << '\n';
    if (X[idx] == 0) {
        X[idx] = x;
    }
    else {
        Y[idx] = x;
    }
}

void distribute(ll sz, vector<int> &X, vector<int> &Y, vector<int> &A, ll idx) {
    // cout << idx << ' ' << sz << ' ' << ex << endl;
    if (idx >= X.size()) {
        X.resize(idx + 1);
    }
    if (idx >= Y.size()) {
        Y.resize(idx + 1);
    }
    // cout << sz << ' ' << e << '\n';
    X[idx] = 0;
    Y[idx] = 0;
    if (sz == 2) {
        connect(INF, X, Y, idx);
        connect(INF, X, Y, idx);
        return;
    }
    X[idx] = nxt;
    nxt--;
    Y[idx] = nxt;
    nxt--;
    distribute(sz / 2, X, Y, A, -X[idx] - 1);
    distribute(sz / 2, X, Y, A, -Y[idx] - 1);
}

void create_circuit(int M, vector<int> A) {
    ll NN = A.size();
    A.push_back(-1);
    ll N = A.size();
    ll y = 0;
    ll ex = 1;
    while (ex < N) {
        ex *= 2;
    }
    while (A.size() < ex) {
        A.push_back(-1);
    }
    N = A.size();
    A[N - 1] = 0;
    vector<int> C, X, Y;
    C.push_back(-1);
    for (int i = 0; i < M; i++) {
        C.push_back(-1);
    }
    distribute(N, X, Y, A, 0);
    // for (int i = 0; i < C.size(); i++) {
    //     cout << C[i] << '\n';
    // }
    // cout << conn << '\n';
    ll pos = 0, cnt = 0;
    vector<bool> state(X.size());
    // for (int i = 0; i < X.size(); i++) {
    //     cout << X[i] << ' ' << Y[i] << endl;
    // }
    do {
        if (pos >= 0) {
            pos = C[pos];
        }
        else {
            if (state[-pos - 1] == 0) {
                if (X[-pos - 1] == INF) {
                    X[-pos - 1] = A[cnt++];
                }
                state[-pos - 1] = !state[-pos - 1];
                pos = X[-pos - 1];
            }
            else {
                if (Y[-pos - 1] == INF) {
                    Y[-pos - 1] = A[cnt++];
                }
                state[-pos - 1] = !state[-pos - 1];
                pos = Y[-pos - 1];
            }
        }
    } while (pos != 0);
    // for (int i = 0; i < X.size(); i++) {
    //     cout << '\t' << X[i] << ' ' << Y[i] << endl;
    // }
    if (X.size() > NN * 2) {
        exit(-1);
        // C[0] = 0;
    }
    answer(C, X, Y);
}

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

doll.cpp: In function 'void distribute(ll, std::vector<int>&, std::vector<int>&, std::vector<int>&, ll)':
doll.cpp:23:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     if (idx >= X.size()) {
      |         ~~~~^~~~~~~~~~~
doll.cpp:26:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     if (idx >= Y.size()) {
      |         ~~~~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:54:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   54 |     while (A.size() < ex) {
      |            ~~~~~~~~~^~~~
doll.cpp:98:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   98 |     if (X.size() > NN * 2) {
      |         ~~~~~~~~~^~~~~~~~
doll.cpp:49:8: warning: unused variable 'y' [-Wunused-variable]
   49 |     ll y = 0;
      |        ^

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56