# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
885257 | 2023-12-09T11:22:19 Z | hugsfromadicto | Unscrambling a Messy Bug (IOI16_messy) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "messy.h" using namespace std; int N; const int MAX=130; void write(int l, int r, int N) { if(l==r) return; string s=""; for(int i=0;i<N;++i) { if(l<=r and i<=r) { s+='0'; } else { s+='1'; } } int mid=(l+r)>>1; for(int i=l;i<=mid;++i) { s[i]='1'; add_element(s); s[i]='0'; } write(l,mid,N); write(mid+1,r,N); } int p[MAX]; void read(int l, int r, vector<int> v, int N) { if(l==r) { p[v[0]]=l; return; } string s=""; for(int i=0;i<n;++i) { s+='1'; } for(int a:v) { s[a]='0'; } int mid=(l+r)>>1; vector<int>left,right; for(int i:v) { s[i]='1'; if(check_element(s)) { left.push_back(i); } else{ right.push_back(i); } s[i]='0'; } read(l, mid, left, N); read(mid + 1, r, right, N); } vector<int> restore_permutation(int N,int w,int r) { write(0,N-1,N); compile_set(); vector<int>tmp; for(int i=0;i<N;++i) { tmp.push_back(i); } read(0,n-1,tmp,N); vector<int>res; for(int i = 0; i < N; i++){ res.push_back(p[i]); } return res; }