제출 #427113

#제출 시각아이디문제언어결과실행 시간메모리
427113ivan24Unscrambling a Messy Bug (IOI16_messy)C++14
0 / 100
2 ms332 KiB
#include "messy.h" #include <bits/stdc++.h> using namespace std; using ll = long long int; typedef vector<ll> vi; typedef vector<vi> vvi; typedef pair<ll,ll> ii; typedef vector<ii> vii; typedef vector<vii> vvii; ll min(ll x, ll y){ return ((x < y) ? x : y); } ll max(ll x, ll y){ return ((x > y) ? x : y); } /* 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) { cout << "add_element: " << x << endl; if (--w < 0 || compiled || !check(x)) { wa(); } set_.insert(x); } bool check_element(string x) { if (--r < 0 || !compiled || !check(x)) { wa(); } bool res = set_.count(x); cout << "check_element: " << x << " " << res << endl; return res; } 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; } */ std::vector<int> restore_permutation(int n, int w, int r) { for (ll i = 1; n > i; i++){ string s; s.assign(n,'0'); for (ll j = 0; i > j; j++){ s[j] = '1'; } add_element(s); } compile_set(); vector<int> p; p.assign(n,-1); vi checked; checked.assign(n,0); for (ll i = 0; n > i; i++){ for (ll j = 0; n > j; j++){ if (checked[j]) continue; string s; s.resize(n); for (ll k = 0; n > k; k++){ if (checked[k] || k == j) s[k] = '1'; else s[k] = '0'; } bool res = check_element(s); if (res){ p[j] = i; checked[j] = true; } } } for (ll i = 0; n > i; i++){ if (!checked[i]) p[i] = n-1; } 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...