제출 #419858

#제출 시각아이디문제언어결과실행 시간메모리
419858PetiUnscrambling a Messy Bug (IOI16_messy)C++14
20 / 100
2 ms460 KiB
#include <bits/stdc++.h> #include "messy.h" using namespace std; const int codeM = 4; vector<int> codes = {5, 7, 10, 11, 13, 14}; void add_start(int n){ string s; s.assign(n, '0'); s[0] = '1'; add_element(s); for(int i = 1; i < codeM; i++){ s.assign(n, '0'); s[i-1] = s[i] = '1'; add_element(s); } } int pos[codeM]; void set_code(string &s, int c){ for(int i = 0; i < codeM; i++) if(c&(1<<i)) s[pos[i]] = '1'; } void add(int l, int r, int x, int n){ if(l+1 >= r) return; int m = (l+r)/2; string s; s.assign(n, '0'); set_code(s, codes[x]); for(int i = l; i < m; i++){ s[i] = '1'; add_element(s); s[i] = '0'; } add(l, m, x+1, n); add(m, r, x+1, n); } int irany[128][6]; bool volt[128] = {}; void get_start(int n){ for(int i = 0; i < n; i++){ string s; s.assign(n, '0'); s[i] = '1'; if(check_element(s)){ pos[0] = i; break; } } volt[0] = true; for(int i = 1; i < codeM; i++){ for(int j = 0; j < n; j++){ if(j == pos[i-1] || volt[j]) continue; string s; s.assign(n, '0'); s[pos[i-1]] = s[j] = '1'; if(check_element(s)){ pos[i] = j; break; } } volt[pos[i]] = true; } } std::vector<int> restore_permutation(int n, int w, int r) { for(int i = 0; i < codeM; i++) pos[i] = i; add_start(n); add(codeM, n, 0, n); //cout<<"added"<<endl; compile_set(); //cout<<"compiled"<<endl; get_start(n); for(int i = 0; i < n; i++) for(int j = 0; j < 6; j++) irany[i][j] = 1; for(int i = 0; i < 6; i++){ string s; s.assign(n, '0'); set_code(s, codes[i]); for(int j = 0; j < n; j++){ if(s[j] == '1') continue; s[j] = '1'; if(check_element(s)) irany[j][i] = 0; s[j] = '0'; } } vector<int> ret(n, -1); for(int i = 0; i < codeM; i++) ret[pos[i]] = i; for(int i = 0; i < n; i++){ if(ret[i] != -1) continue; int l = 4, r = n; for(int j = 0; j < 6; j++){ int m = (l+r)/2; if(irany[i][j]) l = m; else r = m; } ret[i] = l; } return ret; }
#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...