Submission #66343

#	Time	Username	Problem	Language	Result	Execution time	Memory
66343		MANcity	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	5 ms	512 KiB

messy

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "messy.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int n;
int perm[400];
/*add_element("0");
compile_set();
check_element("0");*/
void build(int left,int right)
{
    int m=(left+right)/2;
    fo(i,left,m)
    {
        string s="";
        for1(j,n)
        {
            if(j<left || j>right)
                s+="1";
            if(j==i)
                s+="1";
            if(j!=i && j>=left && j<=right)
                s+="0";
        }
        add_element(s);
    }
    if((right-left)==1)
        return;
    m=(left+right)/2;
    build(left,m);
    build(m+1,right);
}
void query(vector<int> v,int left,int right)
{
    if((right-left)==1)
    {
        string s="";
        for1(j,n)
        {
            if(j==v[1])
                s+="0";
            else
                s+="1";
        }
        int t=check_element(s);
        if(t==1)
        {
            perm[v[0]]=left;
            perm[v[1]]=right;
        }
        else
        {
            perm[v[0]]=right;
            perm[v[1]]=left;
        }
        return;
    }
    int used[200];
    for1(i,n)
        used[i]=0;
    for0(i,v.size()-1)
        used[v[i]]=1;
    vector<int> v1;
    vector<int> v2;
    for0(i,v.size()-1)
    {
        string s="";
        for1(j,n)
        {
            if(used[j]==0)
                s+="1";
            if(used[j]==1)
            {
                if(j==v[i])
                    s+="1";
                else
                    s+="0";
            }
        }
        int t=check_element(s);
        if(t==1)
            v1.push_back(v[i]);
        else
            v2.push_back(v[i]);
    }
    int m=(left+right)/2;
    query(v1,left,m);
    query(v2,m+1,right);
}
vector<int> restore_permutation(int n_0, int w, int r) {
    n=n_0;
    build(1,n);
    compile_set();
    vector<int> v;
    for1(i,n)
        v.push_back(i);
    query(v,1,n);
    vector<int> ANS;
    for1(i,n)
        ANS.pb(perm[i]-1);
    return ANS;
}

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