Submission #1019225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019225		Zbyszek99	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	1 ms	632 KiB

messy

#include <bits/stdc++.h>
using namespace std;
#include "messy.h"

int n;
vector<int> ans;

void set_f(int L, int R, string zap)
{
    if(L == R) return;
    for(int i = L; i <= (L+R)/2; i++) 
    {
        zap[i] = '1';
        add_element(zap);
        zap[i] = '0';
    }
    for(int i = (L+R)/2+1; i <= R; i++)
    {
        zap[i] = '1';
    }
    set_f(L,(L+R)/2,zap);
    for(int i = L ; i <= (L+R)/2; i++)
    {
        zap[i] = '1';
    }
    for(int i = (L+R)/2+1; i <= R; i++)
    {
        zap[i] = '0';
    }
    set_f((L+R)/2+1,R,zap);
}

void ans_f(int L, int R, string zap, vector<int> nums)
{
    if(L == R)
    {
        ans[nums[0]] = L;
        return;
    }
    set<int> good_nums;
    for(auto it: nums)
    {
        zap[it] = '1';
        bool odp = check_element(zap);
        zap[it] = '0';
        if(odp)
        {
            good_nums.insert(it);
        }
    }
    vector<int> nums1;
    vector<int> nums2;
    for(auto& it: nums)
    {
        if(good_nums.find(it) == good_nums.end())
        {
            nums2.push_back(it);
            zap[it] = '1';
        }
        else
        {
            nums1.push_back(it);
            zap[it] = '0';
        }
    }
    ans_f(L,(L+R)/2,zap,nums1);
    for(auto& it: nums)
    {
        if(good_nums.find(it) == good_nums.end())
        {
            zap[it] = '0';
        }
        else
        {
            zap[it] = '1';
        }
    }
    ans_f((L+R)/2+1,R,zap,nums2);
    
}

vector<int> restore_permutation(int N, int w, int r) {
    ans.resize(N);
    n = N;
    string zap = "";
    for(int i = 0; i < n; i++) zap += '0';
    set_f(0,n-1,zap);
    compile_set();
    vector<int> nums;
    for(int i = 0; i < n; i++)
    {
        nums.push_back(i);
    }
    ans_f(0,n-1,zap,nums);
    return ans;
}

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