제출 #740602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
740602		danikoynov	자동 인형 (IOI18_doll)	C++14	100 / 100	188 ms	25292 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2e5 + 10;

int n, m, a[maxn];
vector < int > c, x, y;

struct state
{
    int dev, lf_child, rf_child;

    state()
    {
        dev = 0;
        lf_child = rf_child = -1;
    }
};

state tree[4 * maxn];
int qleft, qright, sum;
int build(int left, int right)
{
    if (left >= qleft && right <= qright)
    {
        sum ++;
        return -1;
    }
    if (left == right)
    {
        sum ++;
        return -1;
    }
    int node = x.size() + 1;
    x.push_back(0);
    y.push_back(0);
    int mid = (left + right) / 2;
    tree[node].lf_child = build(left, mid);
    tree[node].rf_child = build(mid + 1, right);
    x[node - 1] = - tree[node].lf_child;
    y[node - 1] = - tree[node].rf_child;

    //cout << node << " : " << tree[node].lf_child << endl;
    //cout << node << " : " << tree[node].rf_child << endl;
    tree[node].dev = node;
    return node;
}
int pos[4 * maxn];
struct element
{
    int type, idx, val;

    element(int _type, int _idx, int _val)
    {
        type = _type;
        idx = _idx;
        val = _val;
    }

};
vector < element > fin;

bool cmp(element e1, element e2)
{
    if (e1.idx == e2.idx)
        return e1.type < e2.type;
    return e1.idx < e2.idx;
}
bool cmp2(element e1, element e2)
{
    return e1.val < e2.val;
}

void simulate_path(int node, int val)
{
    ///cout << "simulate " << node << " " << val << endl;
    if (pos[node] == 0)
    {
        if (tree[node].lf_child == -1)
        {
            fin.push_back(element(0, node - 1, val));
            ///x[node - 1] = val;
        }
        else
        {
            simulate_path(tree[node].lf_child, val);
        }
        pos[node] = 1;
    }
    else
    {
        if (tree[node].rf_child == -1)
        {
                      fin.push_back(element(1, node - 1, val));
            ///y[node - 1] = val;
        }
        else
        {
            simulate_path(tree[node].rf_child, val);
        }
        pos[node] = 0;
    }
}
void create_circuit(int M, vector<int> A)
{
    n = A.size();
    m = M;
    for (int i = 0; i < A.size(); i ++)
        a[i] = A[i];
     c.resize(m + 1);


    for (int i = 0; i <= m; i ++)
        c[i] = -1;

    int nec = 1;
    while(nec < n + 1)
        nec *= 2;

    qleft = 0;
    qright = (nec - (n  + 1)) - 1;

    int root = build(0, nec - 1);

    for (int i = 0; i < nec; i ++)
        simulate_path(root, i);

    sort(fin.begin(), fin.end(), cmp);
    reverse(fin.begin(), fin.end());
    int rub = nec - (n + 1);

    for (int k = 0; k < rub; k ++)
    {
        element el = fin.back();
        fin.pop_back();
        ///cout << el.idx << " :: " << el.type << endl;

        if (el.type == 0)
            x[el.idx] = - root;
        else
            y[el.idx] =  - root;
    }
    ///cout << sum << " " << fin.size() << endl;
    sort(fin.begin(), fin.end(), cmp2);
    for (int k = 0; k < n + 1; k ++)
    {
        element el = fin[k];
        if (el.type == 0)
            x[el.idx] = a[k];///, cout << "left " << el.idx << " " << a[k] << endl;
        else
            y[el.idx] = a[k];///, cout << "right " << el.idx << " " << a[k] << endl;
    }
    /**for (int i = 0; i <= m; i ++)
    {
        create_node(i);
        continue;

    }*/
    /**cout << "--------------" << endl;
    for (int i = 0; i <= m; i ++)
        cout << c[i] << " ";
    cout << endl;
    cout << "--------------" << endl;
    for (int i = 0; i < x.size(); i ++)
        cout << x[i] << " " << y[i] << endl;*/
    answer(c, x, y);
}

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

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i = 0; i < A.size(); i ++)
      |                     ~~^~~~~~~~~~

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