제출 #1254395

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

messy

# include <iostream>
# include <vector>
# include <algorithm>
# include <random>
using namespace std;
# include "messy.h"
//# include "grader.cpp"

const int MAX=128;

int n;

void build(int l, int r)
{
    if(l==r) return ;

    int mid=(l+r)/2;
    string s(n,'0');
    for(int i=l;i<=r;i++) s[i]='1';
    for(int i=l;i<=mid;i++)
    {
        s[i]='0';
        add_element(s);
        s[i]='1';
    }

    build(l,mid);
    build(mid+1,r);
}

vector<int> perm;

void dc(int l, int r, vector<int> possible)
{
    if(l==r)
    {
        perm[possible[0]]=l;
        return ;
    }

    int mid=(l+r)/2;
    vector<int> left,right;
    string s(n,'0');
    for(int x: possible) s[x]='1';
    for(int x: possible)
    {
        s[x]='0';
        if(check_element(s)) left.push_back(x);
        else right.push_back(x);
        s[x]='1';
    }

    //cout<<l<<" "<<r<<"->"<<left.size()<<" "<<right.size()<<endl;

    dc(l,mid,left);
    dc(mid+1,r,right);
}

std::vector<int> restore_permutation(int N, int w, int r)
{
    n=N;
    build(0,n-1);
    compile_set();

    perm.resize(n);
    vector<int> possible(n);
    for(int i=0;i<n;i++) possible[i]=i;
    dc(0,n-1,possible);

    return perm;

}

/*
4 128 128
0 1 2 3
*/


/*
8 128 128
0 1 2 4 3 5 6 7
*/

/*
8 128 128
3 2 1 4 5 7 6 0
*/

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

messy.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
messy_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30