Submission #67915

#	Time	Username	Problem	Language	Result	Execution time	Memory
67915		Talant	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	4 ms	512 KiB

messy

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

#include <bits/stdc++.h>

#define sc second
#define fr first
#define mk make_pair
#define pb push_back

using namespace std;

const int N = (1e6 + 5);
const int inf = (1e9 + 7);

string s;
vector <int> ans,res;

void fun(int n,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(n,l,md);
      fun(n,md + 1,r);
}
void rec(int n,int l,int r) {
      if (l >= r) return;

      s = "";
      for (int i = 0; i <= n; i ++) s += '0';

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

      vector <int> v1,v2;

      for (int i = l; i <= r; i ++) {
            s[ans[i]] = '1';
            if (check_element(s))
                  v1.pb(ans[i]);
            else
                  v2.pb(ans[i]);
            s[ans[i]] = '0';
      }
      int id = 0,id1 = 0;
      for (int i = l; i <= r; i ++) {
            if (i <= md) ans[i] = v1[id ++];
            else ans[i] = v2[id1 ++];
      }
      rec(n,l,md);
      rec(n,md + 1,r);
}
vector<int> restore_permutation(int n, int w, int r) {
      ans.resize(n);
      res.resize(n);

      n --;

      for (int i = 0; i <= n; i ++)
            ans[i] = i;

      fun(n,0,n);
      compile_set();
      rec(n,0,n);

      for (int i = 0; i <= n; i ++)
            res[ans[i]] = i;

      return res;
}

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