제출 #363452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
363452		mjhmjh1104	Mechanical Doll (IOI18_doll)	C++14	85.55 / 100	145 ms	10184 KiB

doll

#include "doll.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int cnt[200006];
bool sw[400006];
int n, s;
vector<int> c, a, b;

bool goForward(int &x) {
    if (x >= 0) {
        if (c[x] == -2e9) return false;
        x = c[x];
    } else {
        if (!sw[-x - 1]) {
            if (a[-x - 1] == -2e9) return false;
            sw[-x - 1] = true;
            x = a[-x - 1];
        } else {
            if (b[-x - 1] == -2e9) return false;
            sw[-x - 1] = false;
            x = b[-x - 1];
        }
    }
    return true;
}

void create_circuit(int m, vector<int> A) {
    n = (int)A.size();
    c.resize(m + 1);
    for (int i = 0; i < n; i++) cnt[A[i] - 1]++;
    for (int i = 0; i < m + 1; i++) c[i] = -2e9;
    for (int i = 0; i < m; i++) if (cnt[i]) {
        int bit = ceil(log2(cnt[i]));
        int sw_size = 1 << bit;
        int left = sw_size - cnt[i];
        vector<pair<int, int>> sw_cnt, nsw_cnt;
        sw_cnt.push_back({ i + 1, -1 });
        int st_s = -1;
        for (int t = bit - 1; t >= 0; t--) {
            bool rem = false;
            if (left >= 1 << t) {
                left -= 1 << t;
                rem = true;
            }
            nsw_cnt.clear();
            for (int i = 0; i < (int)sw_cnt.size(); i++) {
                if (sw_cnt[i].second == -1) c[sw_cnt[i].first] = -s - 1;
                else if (sw_cnt[i].second == 0) a[sw_cnt[i].first] = -s - 1;
                else b[sw_cnt[i].first] = -s - 1;
                if (rem) {
                    nsw_cnt.push_back({ s, 1 });
                    a.push_back(-st_s - 1);
                    b.push_back(-2e9);
                    rem = false;
                } else {
                    nsw_cnt.push_back({ s, 0 });
                    nsw_cnt.push_back({ s, 1 });
                    a.push_back(-2e9);
                    b.push_back(-2e9);
                }
                if (st_s == -1) st_s = s;
                s++;
            }
            sw_cnt = nsw_cnt;
        }
    }
    A.push_back(0);
    int curr = 0;
    for (int i = 0; i <= n; i++) {
        while (goForward(curr)) ;
        if (curr >= 0) c[curr] = A[i];
        else if (!sw[-curr - 1]) {
            a[-curr - 1] = A[i];
            sw[-curr - 1] = true;
        } else {
            b[-curr - 1] = A[i];
            sw[-curr - 1] = false;
        }
        curr = A[i];
    }
    for (int i = 0; i <= m; i++) if (c[i] == -2e9) c[i] = 0;
    answer(c, a, b);
}

• 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