# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
922381 | 2024-02-05T12:58:51 Z | ByeWorld | Unscrambling a Messy Bug (IOI16_messy) | C++14 | 0 ms | 0 KB |
#include <vector> #include <bits/stdc++.h> #define bupol __builtin_popcount #define ll long long #define ld long double #define fi first #define se second #define pb push_back #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) using namespace std; const int MAXN = 1e3+5; const int MAXK = 205; const int LOG = 20; const int MOD = 1e9+7; const int SQRT = 520; const ll INF = 1e18+10; typedef pair<int,int> pii; typedef pair<pii,int> ipii; #include "messy.h" mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n, R; vector <int> vec, perm; void ADD(){ string s = ""; for(int i=0; i<n; i++) s += '1'; //add_element(s); for(int i=n-1; i>=1; i--){ s[i] = '0'; //cout << s << " oo\n"; add_element(s); } } void CHECK(){ assert(cnt >= R); string s; for(int i=0; i<n; i++) s += '0'; for(int i=0; i<n; i++){ // check yg i (0) perm.clear(); for(int j=0; j<n; j++){ if(vec[j] != -1) continue; perm.pb(j); } shuffle(perm.begin(), perm.end(), rng); for(int j=0; j<perm.size(); j++){ // j='1', i+1->n-1 = '0' s[perm[j]] = '1'; //cout << s << " p\n"; if(check_element(s)){ cnt++; //cout << s << ' ' << j << ' ' << i << " xx\n"; vec[perm[j]] = i; break; } else { s[perm[j]] = '0'; } } } } vector<int> restore_permutation(int N, int w, int r) { n = N; vec.resize(n); R = r; for(int i=0; i<n; i++) vec[i] = -1; ADD(); compile_set(); CHECK(); for(int i=0; i<n; i++) if(vec[i]==-1) vec[i] = n-1; return vec; }