Submission #1244508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244508		Ice_man	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	1 ms	584 KiB

messy

#include <vector>
#include <iostream>

#define maxn 1000
#include "messy.h"



void _fill(std::string s, int l, int r)
{
    if(l == r)
        return;

    //std::cout << "!! " << l << " " << r << "\n";

    int mid = (l + r) / 2;

    for(int i = l; i <= mid; i++)
    {
        s[i] = '1';
        add_element(s);

        //std::cout << s << "\n";

        s[i] = '0';
    }

    for(int i = l; i <= mid; i++)
        s[i] = '1';
    _fill(s, mid + 1, r);

    for(int i = l; i <= mid; i++)
        s[i] = '0';
    for(int i = mid + 1; i <= r; i++)
        s[i] = '1';
    _fill(s , l , mid);
}




std::vector <int> ans;
std::vector <int> ret;
void rec(std::string s , int l , int r , std::vector <int> can)
{
    if(l == r)
    {
        ans[l] = can.back();
        return;
    }

    std::vector <int> left;
    std::vector <int> right;


    for(auto& e : can)
    {
        s[e] = '1';
        bool lamp = check_element(s);
        s[e] = '0';

        if(lamp == true)
            left.push_back(e);
        else
            right.push_back(e);
    }

    int mid = (l + r) / 2;

    for(auto& e : right)
        s[e] = '1';
    rec(s , l , mid , left);

    for(auto& e : left)
        s[e] = '1';
    for(auto& e : right)
        s[e] = '0';

    rec(s , mid + 1 , r , right);
}




std::string s;

std::vector<int> restore_permutation(int n, int w, int r)
{
    ans.resize(n);
    ret.resize(n);
    for(int i = 0; i < n; i++)
      s += '0';
    _fill(s , 0 , n - 1);

    compile_set();

    std::vector <int> help;
    for(int i = 0; i < n; i++)
      help.push_back(i);

    rec(s , 0 , n - 1 , help);
    for(int i = 0; i < n; i++)
        ret[ans[i]] = i;

    //for(auto& e : ret)
      //std::cout << e << " ";
    //std::cout << "\n";


    return ret;
}

Compilation message (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