# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
140467 | 2019-08-03T08:01:22 Z | MrBrionix | Unscrambling a Messy Bug (IOI16_messy) | C++14 | 4 ms | 636 KB |
#include <vector> #include <cstdio> #include <string> #include <set> #include <cstdlib> #include <iostream> #include <bits/stdc++.h> #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; } 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<<x<<endl; 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; } */ vector<int> sol,v[16][200],opz[16][200]; string vuota,s; int cont; vector<int> restore_permutation(int n, int w, int r) { for(int i=0;i<n;i++){ vuota.push_back('0'); v[0][0].push_back(i); } s=vuota; for(int i=0;v[i][0].size()>1;i++){ for(int j=0;j<(1<<i);j++){ for(int z=0;z<(v[i][j].size()/2);z++){ v[i+1][j*2].push_back(v[i][j][z]); v[i+1][j*2+1].push_back(v[i][j][z+(v[i][j].size()/2)]); } } } for(int i=0;i<n/2;i++){ s[i]='1'; add_element(s); s[i]='0'; } for(int i=1;v[i][0].size()>1;i++){ for(int j=0;j<(1<<i);j++){ s=vuota; for(int z=0;z<v[i][(j+1)%(1<<i)].size();z++){ s[v[i][(j+1)%(1<<i)][z]]='1'; } for(int z=0;z<(v[i][j].size()/2);z++){ s[v[i][j][z]]='1'; add_element(s); s[v[i][j][z]]='0'; } } } compile_set(); s=vuota; for(int i=0;i<v[0][0].size();i++){ s[i]='1'; if(check_element(s)) opz[1][0].push_back(i); else opz[1][1].push_back(i); s[i]='0'; } cont=1; //cout<<"a"<<endl; for(;opz[cont][0].size()>1;cont++){ for(int j=0;j<(1<<cont);j++){ s=vuota; for(int z=0;z<opz[cont][(j+1)%(1<<cont)].size();z++){ s[opz[cont][(j+1)%(1<<cont)][z]]='1'; //cout<<z<<" z"<<endl; } for(int z=0;z<opz[cont][j].size();z++){ s[opz[cont][j][z]]='1'; if(check_element(s)) opz[cont+1][j*2].push_back(opz[cont][j][z]); else opz[cont+1][j*2+1].push_back(opz[cont][j][z]); s[opz[cont][j][z]]='0'; } //cout<<j<<" j"<<endl; } //cout<<cont<<endl; } sol.resize(n); for(int i=0;i<n;i++){ sol[opz[cont][i][0]]=i; } return sol; } /* 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; }*/
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | n = 8 |
2 | Correct | 2 ms | 504 KB | n = 8 |
3 | Correct | 2 ms | 504 KB | n = 8 |
4 | Correct | 2 ms | 424 KB | n = 8 |
5 | Correct | 2 ms | 504 KB | n = 8 |
6 | Correct | 2 ms | 504 KB | n = 8 |
7 | Correct | 2 ms | 504 KB | n = 8 |
8 | Correct | 2 ms | 632 KB | n = 8 |
9 | Correct | 2 ms | 504 KB | n = 8 |
10 | Correct | 3 ms | 508 KB | n = 8 |
11 | Correct | 3 ms | 504 KB | n = 8 |
12 | Correct | 2 ms | 504 KB | n = 8 |
13 | Correct | 3 ms | 504 KB | n = 8 |
14 | Correct | 3 ms | 504 KB | n = 8 |
15 | Correct | 2 ms | 508 KB | n = 8 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 508 KB | n = 32 |
2 | Correct | 2 ms | 508 KB | n = 32 |
3 | Correct | 2 ms | 544 KB | n = 32 |
4 | Correct | 2 ms | 504 KB | n = 32 |
5 | Correct | 2 ms | 508 KB | n = 32 |
6 | Correct | 2 ms | 504 KB | n = 32 |
7 | Correct | 2 ms | 504 KB | n = 32 |
8 | Correct | 2 ms | 504 KB | n = 32 |
9 | Correct | 2 ms | 504 KB | n = 32 |
10 | Correct | 2 ms | 504 KB | n = 32 |
11 | Correct | 2 ms | 504 KB | n = 32 |
12 | Correct | 2 ms | 504 KB | n = 32 |
13 | Correct | 2 ms | 504 KB | n = 32 |
14 | Correct | 2 ms | 504 KB | n = 32 |
15 | Correct | 3 ms | 504 KB | n = 32 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | n = 32 |
2 | Correct | 2 ms | 508 KB | n = 32 |
3 | Correct | 2 ms | 504 KB | n = 32 |
4 | Correct | 2 ms | 504 KB | n = 32 |
5 | Correct | 2 ms | 504 KB | n = 32 |
6 | Correct | 2 ms | 504 KB | n = 32 |
7 | Correct | 2 ms | 504 KB | n = 32 |
8 | Correct | 2 ms | 504 KB | n = 32 |
9 | Correct | 2 ms | 504 KB | n = 32 |
10 | Correct | 2 ms | 504 KB | n = 32 |
11 | Correct | 2 ms | 504 KB | n = 32 |
12 | Correct | 2 ms | 504 KB | n = 32 |
13 | Correct | 3 ms | 504 KB | n = 32 |
14 | Correct | 2 ms | 544 KB | n = 32 |
15 | Correct | 2 ms | 504 KB | n = 32 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 636 KB | n = 128 |
2 | Correct | 4 ms | 632 KB | n = 128 |
3 | Correct | 4 ms | 632 KB | n = 128 |
4 | Correct | 4 ms | 632 KB | n = 128 |
5 | Correct | 4 ms | 632 KB | n = 128 |
6 | Correct | 4 ms | 632 KB | n = 128 |
7 | Correct | 4 ms | 632 KB | n = 128 |
8 | Correct | 4 ms | 632 KB | n = 128 |
9 | Correct | 4 ms | 632 KB | n = 128 |
10 | Correct | 4 ms | 632 KB | n = 128 |
11 | Correct | 4 ms | 632 KB | n = 128 |
12 | Correct | 4 ms | 632 KB | n = 128 |
13 | Correct | 4 ms | 632 KB | n = 128 |
14 | Correct | 4 ms | 632 KB | n = 128 |
15 | Correct | 4 ms | 632 KB | n = 128 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 636 KB | n = 128 |
2 | Correct | 4 ms | 632 KB | n = 128 |
3 | Correct | 4 ms | 632 KB | n = 128 |
4 | Correct | 4 ms | 632 KB | n = 128 |
5 | Correct | 4 ms | 632 KB | n = 128 |
6 | Correct | 4 ms | 632 KB | n = 128 |
7 | Correct | 4 ms | 632 KB | n = 128 |
8 | Correct | 4 ms | 632 KB | n = 128 |
9 | Correct | 4 ms | 632 KB | n = 128 |
10 | Correct | 4 ms | 632 KB | n = 128 |
11 | Correct | 4 ms | 632 KB | n = 128 |
12 | Correct | 4 ms | 632 KB | n = 128 |
13 | Correct | 4 ms | 632 KB | n = 128 |
14 | Correct | 4 ms | 632 KB | n = 128 |
15 | Correct | 3 ms | 632 KB | n = 128 |