제출 #1254106

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

messy

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

const int MAX=128;

int n,LOG;

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

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

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

int find_level(int x, int y, int l=0, int r=n-1, int level=0)
{
    int mid=(l+r)/2;
    if(x<=mid and mid<y) return level;
    if(y<=mid) return find_level(x,y,l,mid,level+1);
    else return find_level(x,y,mid+1,r,level+1);

}

bool check(int x, int y, int l=0, int r=n-1)
{
    int mid=(l+r)/2;
    if(x<=mid and mid<y)
    {
        string s(n,'0');
        for(int i=l;i<=mid;i++) s[i]='1';
        swap(s[x],s[y]);

        return check_element(s);
    }

    if(y<=mid) return check(x,y,l,mid);
    else return check(x,y,mid+1,r);
}

std::vector<int> restore_permutation(int N, int w, int r)
{
    n=N;
    LOG=31-__builtin_clz(n);

    build(0,n-1);
    compile_set();

    for(int k=0;k<LOG;k++)
    for(int x=0;x<n;x++)
    {
        for(int y=x+1;y<n;y++)
        {
            if(find_level(x,y)!=k) continue;
            if(check(x,y))
            {
                vector<int> ans;
                for(int i=0;i<n;i++) ans.push_back(i);
                swap(ans[x],ans[y]);
                return ans;
            }
        }
    }


    vector<int> ans;
    for(int i=0;i<n;i++) ans.push_back(i);
    return ans;
}

/*
4 128 128
0 1 2 3
*/


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

컴파일 시 표준 에러 (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: 0 / 18
• Subtask 3: 0 / 11
• Subtask 4: 0 / 21
• Subtask 5: 0 / 30