Submission #67587

#	Time	Username	Problem	Language	Result	Execution time	Memory
67587		mirbek01	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	3 ms	640 KiB

messy

#include <bits/stdc++.h>

#include "messy.h"
//#include "grader.cpp"

using namespace std;

int n;
string s;
vector <int> ans, vv;

void fun(int l, int r){
      if(l >= r) return ;
      s = "";

      for(int i = 0; i < n; i ++){
            if(l <= i && i <= r)
                  s += '0';
            else
                  s += '1';
      }
      int md = (l + r) >> 1;
      for(int i = l; i <= md; i ++){
            s[i] = '1';
            add_element(s);
            s[i] = '0';
      }
      fun(l, md);
      fun(md + 1, r);
}

void rec(int l, int r){
      if(l >= r){
            return ;
      }
      s.resize(n);
      for(int i = 0; i < n; i ++){
            if(l <= i && i <= r)
                  s[ans[i]] = '0';
            else
                  s[ans[i]] = '1';
      }
      vector < int > v1, v2;
      int md = (l + r) >> 1;
      for(int i = l; i <= r; i ++){
            s[ans[i]] = '1';
            if(check_element(s))
                  v1.push_back(ans[i]);
            else
                  v2.push_back(ans[i]);
            s[ans[i]] = '0';
      }
      int p1 = 0, p2 = 0;
      for(int i = l; i <= r; i ++){
            if(i <= md){
                  ans[i] = v1[p1 ++];
            } else {
                  ans[i] = v2[p2 ++];
            }
      }
      rec(l, md);
      rec(md + 1, r);
}

vector<int> restore_permutation(int NN, int w, int r) {
      n = NN;
      ans.resize(n);
      vv.resize(n);
      for(int i = 0; i < n; i ++)
            ans[i] = i;
      fun(0, n - 1);
      compile_set();
      rec(0, n - 1);
      for(int i = 0; i < n; i ++){
            vv[ans[i]] = i;
      }
      return vv;
}

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