This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
~~~~~~~~~~~~~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |