제출 #836552

#제출 시각아이디문제언어결과실행 시간메모리
836552VictorUnscrambling a Messy Bug (IOI16_messy)C++17
100 / 100
2 ms468 KiB
#include "messy.h" #include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(b)-1;i>=(a);i--) #define trav(a,x) for(auto&a:x) #define all(x) x.begin(),x.end() #define sz(x) ll(x.size()) #define pb push_back typedef long long ll; typedef pair<ll,ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; ll logn; std::vector<int> restore_permutation(int n, int w, int r) { vll ids,nums; rep(i,0,n) { ids.pb(i); nums.pb(i); } logn=__builtin_ctz(n); { string s=string(n,'0'); rep(i,0,n/2) { s[i]='1'; add_element(s); s[i]='0'; } } vector<vll> groups; { rep(j,0,2) { vll group; rep(i,0+j*(n/2),n/2+j*(n/2)) group.pb(i); groups.pb(group); } } rep(i,1,logn) { ll k=sz(groups); for(int j=0;j<k;j+=2) { vll g1=groups[j]; vll g2=groups[j+1]; rep(a,0,2) { string el=string(n,'0'); trav(val,g2) el[val]='1'; rep(b,0,sz(g1)/2) { el[g1[b]]='1'; add_element(el); el[g1[b]]='0'; } g1.swap(g2); } } vector<vll> ngroups; trav(group,groups) { rep(j,0,2) { vll ngroup; rep(a,0,sz(group)/2) ngroup.pb(group[a+j*sz(group)/2]); ngroups.pb(ngroup); } } groups.swap(ngroups); } compile_set(); groups.assign(2,vll()); { string el=string(n,'0'); rep(i,0,n) { el[i]='1'; groups[!check_element(el)].pb(i); el[i]='0'; } } //trav(group,groups) { // trav(val,group) cout<<val<<' '; // cout<<endl; //} rep(i,1,logn) { ll k=sz(groups); vector<vll> ngroups; for(int j=0;j<k;j+=2) { vll g1=groups[j]; vll g2=groups[j+1]; rep(a,0,2) { string el=string(n,'0'); trav(val,g2) el[val]='1'; vll ng1,ng2; trav(val,g1) { el[val]='1'; //cout<<"el = "<<el<<" check = "<<check_element(el)<<endl; if(check_element(el)) ng1.pb(val); else ng2.pb(val); el[val]='0'; } ngroups.pb(ng1); ngroups.pb(ng2); g1.swap(g2); } } groups.swap(ngroups); } vector<int> ans(n); rep(i,0,n) ans[groups[i][0]]=i; //cout<<sz(groups)<<endl; //cout<<sz(groups[0])<<endl; //cout<<"ans = "; //rep(i,0,n) cout<<ans[i]<<' '; //cout<<endl; return ans; } /* #include <vector> #include <cstdio> #include <string> #include <set> #include <cstdlib> #include <iostream> #include "messy.h" using namespace std; namespace helper { set<string> set_; bool compiled = false; int n; vector<int> p; int w; int r; int read_int() { int x; cin >> x; return x; } } using namespace helper; // A convenience function. int get_p(int i) { int ret = p[i]; return ret; } int main() { n = read_int(); w = read_int(); r = read_int(); p = vector<int>(n); for (int i = 0; i < n; i++) { p[i] = read_int(); } vector<int> answer = restore_permutation(n, w, r); if (answer.size() != n) { printf("WA\n"); return 0; } printf("%d", answer[0]); for (int i = 1; i < n; i++) { printf(" %d", answer[i]); } printf("\n"); return 0; } void wa() { printf("WA\n"); exit(0); } bool check(const string& x) { if ((int)x.length() != n) { return false; } for (int i = 0; i < n; i++) { if (x[i] != '0' && x[i] != '1') { return false; } } return true; } void add_element(string x) { if (--w < 0 || compiled || !check(x)) { wa(); } set_.insert(x); } bool check_element(string x) { if (--r < 0 || !compiled || !check(x)) { wa(); } return set_.count(x); } void compile_set() { if (compiled) { wa(); } compiled = true; set<string> compiledSet; string compiledElement = string(n, ' '); for (set<string>::iterator it = set_.begin(); it != set_.end(); it++) { string s = *it; for (int i = 0; i < n; i++) { compiledElement[i] = s[get_p(i)]; } compiledSet.insert(compiledElement); } set_ = compiledSet; }*/
#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...