Submission #568255

#TimeUsernameProblemLanguageResultExecution timeMemory
568255hoanghq2004Unscrambling a Messy Bug (IOI16_messy)C++14
20 / 100
2 ms468 KiB
#include <bits/stdc++.h> #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include "messy.h" using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>; // // //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; // // //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); //} //int get_p(int i) { // int ret = p[i]; // return ret; //} // //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> restore_permutation(int n, int w, int r) { function <void(int, int)> add = [&](int L, int R) { if (L == R) return; int mid = L + R >> 1; string s(n, '1'); for (int i = L; i <= R; ++i) s[i] = '0'; // cout << L << ' ' << R << "aa\n"; for (int i = L; i <= mid; ++i) { s[i] = '1'; add_element(s); // cout << s << ' ' << L << ' ' << R << '\n'; s[i] = '0'; } add(L, mid); add(mid + 1, R); }; add(0, n - 1); // exit(0); compile_set(); vector <int> ans(n); function <void(int, int, vector <int>)> divide = [&](int L, int R, vector <int> p) { if (L == R) { assert(p.size() == 1); ans[L] = p[0]; return; } int mid = L + R >> 1; string s(n, '1'); vector <int> lft, rgt; for (auto x: p) s[x] = '0'; for (auto x: p) { s[x] = '1'; if (!check_element(s)) rgt.push_back(x); else lft.push_back(x); s[x] = '0'; } divide(L, mid, lft); divide(mid + 1, R, rgt); }; vector <int> p; for (int i = 0; i < n; ++i) p.push_back(i); divide(0, n - 1, p); return ans; } // // //// A convenience function. // //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 (stderr)

messy.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
messy.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
messy.cpp: In lambda function:
messy.cpp:92:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |         int mid = L + R >> 1;
      |                   ~~^~~
messy.cpp: In lambda function:
messy.cpp:115:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |         int mid = L + R >> 1;
      |                   ~~^~~
#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...