제출 #1360618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1360618		NValchanov	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	1 ms	580 KiB

messy

#include <bits/stdc++.h>

#include "messy.h"

using namespace std;

int n;
vector < int > p;

void dnc_add(int left, int right)
{
    if(left == right)
        return;

    int mid = left + (right - left) / 2;

    string test;

    for(int i = 0; i < n; i++)
    {
        test += '1';
    }

    for(int i = left; i <= right; i++)
    {
        test[i] = '0';
    }

    for(int i = left; i <= mid; i++)
    {
        test[i] = '1';
        add_element(test);
        test[i] = '0';
    }

    dnc_add(left, mid);
    dnc_add(mid + 1, right);
}

void dnc_check(int left, int right, vector < int > idxs)
{
    if(left == right)
    {
        p[idxs.back()] = left;
        return; 
    }

    int mid = left + (right - left) / 2;
    vector < int > idxs_left;
    vector < int > idxs_right;

    string test;

    for(int i = 0; i < n; i++)
    {
        test += '1';
    }

    for(int idx : idxs)
    {
        test[idx] = '0';
    }

    for(int idx : idxs)
    {
        test[idx] = '1';

        if(check_element(test))
        {
            idxs_left.push_back(idx);
        }
        else
        {
            idxs_right.push_back(idx);
        }

        test[idx] = '0';
    }

    dnc_check(left, mid, idxs_left);
    dnc_check(mid + 1, right, idxs_right);
}

vector < int > restore_permutation(int N, int w, int r) 
{
    n = N;
    p.resize(n);

    vector < int > idxs(n);

    for(int i = 0; i < n; i++)
    {
        idxs[i] = i;
    }

    dnc_add(0, n - 1);
    compile_set();
    dnc_check(0, n - 1, idxs);

    return p;
}

• 서브태스크 1: 20 / 20
• 서브태스크 2: 18 / 18
• 서브태스크 3: 11 / 11
• 서브태스크 4: 21 / 21
• 서브태스크 5: 30 / 30