Submission #94577

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

messy

#include <bits/stdc++.h>
#include "messy.h"

using namespace std;

vector<int> restore_permutation(int n, int w, int r) {
  for (int i = n >> 1; i; i >>= 1) {
    for (int j = 0; j < n; j += i << 1) {
      string s(n, '0');
      for (int k = 0; k < i << 1; ++k) {
        s[j + k] = '1';
      }
      for (int k = 0; k < i; ++k) {
        s[j + k + i] = '0';
        add_element(s);
        s[j + k + i] = '1';
      }
    }
  }
  compile_set();
  vector<int> p(n);
  for (int i = 0; i < n; ++i) {
    p[i] = i;
  }
  for (int i = n >> 1; i; i >>= 1) {
    for (int j = 0; j < n; j += i << 1) {
      string s(n, '0');
      for (int k = 0; k < i << 1; ++k) {
        s[p[j + k]] = '1';
      }
      vector<int> left, right;
      for (int k = 0; k < i << 1; ++k) {
        s[p[j + k]] = '0';
        if (check_element(s)) {
          right.push_back(p[j + k]);
        } else {
          left.push_back(p[j + k]);
        }
        s[p[j + k]] = '1';
      }
      for (int k = 0; k < i; ++k) {
        p[j + k] = left[k];
        p[j + k + i] = right[k];
      }
    }
  }
  vector<int> ans(n);
  for (int i = 0; i < n; ++i) {
    ans[p[i]] = i;
  }
  return ans;
}

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