Submission #1196110

#TimeUsernameProblemLanguageResultExecution timeMemory
1196110lrnnzUnscrambling a Messy Bug (IOI16_messy)C++17
100 / 100
3 ms584 KiB
#include <bits/stdc++.h> #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <iomanip> #include "messy.h" using namespace std; #define all(a) (a).begin(), (a).end() #define sz(a) (int)(a).size() #define ll long long #define ld long double #define ui uint64_t #define cont(set, element) ((set).find(element) != (set).end()) /********* DEBUG *********/ template <typename T> void outvec(const vector<T>& Z){ for (const T& x : Z) cout << x << ' '; cout << "\n"; } void printVariable(const any& var) { if (!var.has_value()) { cout << "null"; return; } if (var.type() == typeid(int)) { cout << any_cast<int>(var); } else if (var.type() == typeid(double)) { cout << any_cast<double>(var); } else if (var.type() == typeid(float)) { cout << any_cast<float>(var); } else if (var.type() == typeid(char)) { cout << any_cast<char>(var); } else if (var.type() == typeid(bool)) { cout << (any_cast<bool>(var) ? "true" : "false"); } else if (var.type() == typeid(string)) { cout << any_cast<string>(var); } else if (var.type() == typeid(const char*)) { cout << any_cast<const char*>(var); } else if (var.type() == typeid(long long)) { cout << any_cast<long long>(var); } else { cout << "[unknown type]"; } } template<typename... Args> void outval(Args... args) { vector<any> variables = {args...}; for (size_t i = 0; i < variables.size(); ++i) { printVariable(variables[i]); if (i != variables.size() - 1) { cout << " "; } } cout << "\n"; } #define nl "\n" #define sp << " " << /********* DEBUG *********/ const ll MOD = 1000000007; const ll inf = 1e18; const ll mxN = 1000005; ll _r=0,_w=0; // divide and conquer vector<int> ans; void inserts(int n, int l, int r){ string curr = ""; ll len = (r-l+1)/2; //outval("len:",len); for (int i = 0; i < len; i++){ curr=""; for (int j = 0; j < n; j++){ if (j < l || j > r || j == l + i) curr+='1'; else curr += '0'; } //outval("curr:",curr); add_element(curr); } if (len >= 2) inserts(n, l, r-len), inserts(n, l+len, r); } void answers(int n, int l, int r, set<int> idxs){ if (l == r){ for (auto &x : idxs) ans[x] = l; return; } string curr = ""; set<int> leftidxs; ll cnt = 0; for (auto &x : idxs){ curr = ""; for (int i = 0; i < n; i++){ if (i == x || !cont(idxs, i)) curr += '1'; else curr += '0'; } //outval("curr:",curr); if (check_element(curr)) leftidxs.insert(x);//, outval("in:",x); } for (auto &x : leftidxs) idxs.erase(x); ll len = (r-l+1)/2; answers(n, l, r-len, leftidxs); answers(n, l + len, r, idxs); } vector<int> restore_permutation(int n, int w, int r) { ans.resize(n); inserts(n, 0, n-1); compile_set(); set<int> temp; for (int i = 0; i < n; i++) temp.insert(i); answers(n, 0, n-1, temp); return ans; }

Compilation message (stderr)

messy.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
messy_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...