제출 #1124440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124440		Pacybwoah	자동 인형 (IOI18_doll)	C++20	10 / 100	29 ms	5048 KiB

doll

#include "doll.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
namespace{
    int n, m, cnt = 1;
    vector<int> c, x, y;
    int sl, sr;
    vector<pair<pair<int, int>, int>> leaves;
    int build(int l, int r, int ind, int dep, bool flag){
        if(r < sl || l == r){
            leaves.push_back(make_pair(make_pair(ind, cnt - 1), (int)flag));
            return 0;
        }
        int mid = (l + r) >> 1;
        int cur = cnt;
        cnt++;
        x[cur - 1] = -build(l, mid, ind, dep + 1, 0);
        y[cur - 1] = -build(mid + 1, r, ind + (1 << dep), dep + 1, 1);
        return cur;
    }
}

void create_circuit(int M, std::vector<int> A){
    m = M;
    n = A.size();
    c.resize(m + 1);
    x.resize(n + 50);
    y.resize(n + 50);
    fill(x.begin(), x.end(), 12345678);
    fill(y.begin(), y.end(), 12345678);
    int dep = 1;
    while((1 << dep) < n) dep++;
    sr = (1 << dep);
    sl = sr - n + 1;
    int fst = A[0];
    c[fst] = -build(1, sr, 0, 0, 0);
    c[0] = fst;
    sort(leaves.begin(), leaves.end());
    reverse(leaves.begin(), leaves.end());
    A.push_back(0);
    reverse(A.begin(), A.end());
    A.pop_back();
    int sz = (int)leaves.size();
    for(int i = 1; i <= m; i++) c[i] = c[fst];
    for(int i = 0; i < n; i++){
        auto &[leaf, flag] = leaves[i];
        //cout << leaf.first << ' ' << leaf.second << " " << A[i] << "\n";
        if(flag == 0) x[leaf.second - 1] = A[i];
        else y[leaf.second - 1] = A[i];
    }
    for(int i = n; i < sz; i++){
        auto &[leaf, flag] = leaves[i];
        if(flag == 0) x[leaf.second - 1] = c[fst];
        else y[leaf.second - 1] = c[fst];
    }
    while(!x.empty() && x.back() == 12345678) x.pop_back();
    while(!y.empty() && y.back() == 12345678) y.pop_back();
    /*for(auto &hi: c) cout << hi << ' ';
    cout << "\n";
    for(auto &hi: x) cout << hi << " ";
    cout << "\n";
    for(auto &hi: y) cout << hi << " ";
    cout << "\n";*/
    answer(c, x, y);
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp doll.cpp

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