Submission #42807

#TimeUsernameProblemLanguageResultExecution timeMemory
42807funcsrUnscrambling a Messy Bug (IOI16_messy)C++14
100 / 100
5 ms512 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...