Submission #568256

#	Time	Username	Problem	Language	Result	Execution time	Memory
568256		hoanghq2004	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	3 ms	468 KiB

messy

#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) {
            ans[p[0]] = L;
            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:114:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |         int mid = L + R >> 1;
      |                   ~~^~~

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30