Submission #42807

#	Time	Username	Problem	Language	Result	Execution time	Memory
42807		funcsr	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	5 ms	512 KiB

messy

#include "messy.h"
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define INF 1145141919
#define pb push_back
#define _1 first
#define _2 second

int writes = 0, reads = 0;
void add(string s) {
  writes++;
  add_element(s);
}
bool check(string s) {
  reads++;
  return check_element(s);
}
vector<int> restore_permutation(int n, int w, int r) {
  int x = n;
  int logn = 0;
  while (x>=2) logn++, x/=2;
  assert(logn < n-logn);
  string zeros(n, '0');
  rep(i, logn) {
    zeros[i] = '1';
    add(zeros);
    zeros[i] = '0';
  }
  string ones(n, '1');
  rep(i, logn) {
    ones[i] = '0';
    add(ones);
  }
  for (int i=logn; i<n; i++) {
    string zeros(n, '0');
    zeros[i] = '1';
    rep(k, logn) if ((i>>k)&1) {
      zeros[k] = '1';
      add(zeros);
    }
  }

  compile_set();
  vector<int> ret(n, -1), rev(n, -1);

  vector<int> special;
  rep(i, n) {
    zeros[i] = '1';
    if (check(zeros)) special.pb(i);
    zeros[i] = '0';
  }
  assert(special.size() == logn);

  string pat(n, '1');
  rep(i, logn) {
    int pos = -1;
    for (int p : special) if (pat[p] == '1') {
      pat[p] = '0';
      if (check(pat)) {
        pos = p;
        break;
      }
      pat[p] = '1';
    }
    assert(pos != -1 && rev[pos] == -1);
    ret[i] = pos;
    rev[pos] = i;
    pat[pos] = '0';
  }
  map<string, set<int> > cnt;
  for (int i=logn; i<n; i++) {
    string o = "";
    cnt[o].insert(i);
    rep(j, logn) {
      o += ((i>>j)&1)?'1':'0';
      cnt[o].insert(i);
    }
  }
  rep(i, n) if (rev[i] == -1) {
    string s(n, '0');
    s[i] = '1';
    int pos = 0;
    string prefix = "";
    rep(j, logn) {
      assert(!cnt[prefix].empty());
      if (cnt[prefix].size() == 1) {
        pos = *cnt[prefix].begin();
        break;
      }
      s[ret[j]] = '1';
      if (check(s)) {
        prefix += '1';
        pos |= 1<<j;
      }
      else {
        prefix += '0';
        s[ret[j]] = '0';
      }
    }
    for (auto &p : cnt) p._2.erase(pos);
    assert(ret[pos] == -1);
    ret[pos] = i;
    rev[i] = pos;
  }
  return rev;
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from messy.cpp:7:
messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:58:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(special.size() == logn);
          ~~~~~~~~~~~~~~~^~~~

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