제출 #69502

#제출 시각아이디문제언어결과실행 시간메모리
69502funcsrUnscrambling a Messy Bug (IOI16_messy)C++17
100 / 100
4 ms512 KiB
#include "messy.h" #include <vector> #include <iostream> #include <algorithm> #include <cassert> #define rep(i, n) for (int i=0; i<(n); i++) #define pb push_back #define INF (1LL<<60) #define all(x) (x).begin(), (x).end() #define _1 first #define _2 second using namespace std; int N; vector<int> ret; // [l, r) void prepare(int l, int r) { if (r-l == 1) return; rep(i, (r-l)/2) { string q(N, '1'); for (int x=l; x<r; x++) q[x] = '0'; q[l+i] = '1'; add_element(q); //cout<<"!"<<q<<" ["<<l<<","<<r<<")\n"; } prepare(l, (l+r)/2); prepare((l+r)/2, r); } void solve(vector<int> pos) { //cout<<"solve({";for(int x:pos)cout<<x<<",";cout<<"})\n"; int len = pos.size(); if (len == 1) { ret.pb(pos[0]); return; } vector<int> left, right; rep(i, len) { string q(N, '1'); rep(j, len) q[pos[j]] = '0'; q[pos[i]] = '1'; //cout<<q<<"?\n"; if (check_element(q)) left.pb(pos[i]); else right.pb(pos[i]); } assert(left.size() == right.size()); solve(left); solve(right); } vector<int> restore_permutation(int NN, int W, int R) { N = NN; prepare(0, N); compile_set(); vector<int> all; rep(i, N) all.pb(i); solve(all); vector<int> p(N); rep(i, N) p[ret[i]] = i; return p; }
#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...