oj.uz

답안 #568256

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
568256 2022-05-25T03:26:33 Z hoanghq2004 Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 3 ms 468 KB 
#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

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.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB n = 8
2 Correct 0 ms 212 KB n = 8
3 Correct 0 ms 212 KB n = 8
4 Correct 1 ms 212 KB n = 8
5 Correct 0 ms 212 KB n = 8
6 Correct 0 ms 212 KB n = 8
7 Correct 1 ms 212 KB n = 8
8 Correct 1 ms 212 KB n = 8
9 Correct 0 ms 216 KB n = 8
10 Correct 1 ms 212 KB n = 8
11 Correct 0 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 0 ms 212 KB n = 8
14 Correct 0 ms 212 KB n = 8
15 Correct 0 ms 212 KB n = 8

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB n = 32
2 Correct 1 ms 212 KB n = 32
3 Correct 1 ms 296 KB n = 32
4 Correct 1 ms 304 KB n = 32
5 Correct 1 ms 212 KB n = 32
6 Correct 1 ms 212 KB n = 32
7 Correct 1 ms 212 KB n = 32
8 Correct 1 ms 212 KB n = 32
9 Correct 1 ms 300 KB n = 32
10 Correct 1 ms 212 KB n = 32
11 Correct 1 ms 212 KB n = 32
12 Correct 1 ms 212 KB n = 32
13 Correct 1 ms 212 KB n = 32
14 Correct 1 ms 300 KB n = 32
15 Correct 1 ms 212 KB n = 32

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB n = 32
2 Correct 1 ms 212 KB n = 32
3 Correct 1 ms 212 KB n = 32
4 Correct 0 ms 212 KB n = 32
5 Correct 1 ms 300 KB n = 32
6 Correct 1 ms 212 KB n = 32
7 Correct 1 ms 212 KB n = 32
8 Correct 1 ms 212 KB n = 32
9 Correct 1 ms 212 KB n = 32
10 Correct 1 ms 212 KB n = 32
11 Correct 1 ms 212 KB n = 32
12 Correct 1 ms 212 KB n = 32
13 Correct 1 ms 296 KB n = 32
14 Correct 1 ms 212 KB n = 32
15 Correct 1 ms 296 KB n = 32

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB n = 128
2 Correct 2 ms 432 KB n = 128
3 Correct 2 ms 428 KB n = 128
4 Correct 1 ms 468 KB n = 128
5 Correct 2 ms 468 KB n = 128
6 Correct 2 ms 468 KB n = 128
7 Correct 2 ms 468 KB n = 128
8 Correct 2 ms 468 KB n = 128
9 Correct 2 ms 428 KB n = 128
10 Correct 2 ms 468 KB n = 128
11 Correct 2 ms 468 KB n = 128
12 Correct 3 ms 468 KB n = 128
13 Correct 2 ms 428 KB n = 128
14 Correct 2 ms 468 KB n = 128
15 Correct 2 ms 468 KB n = 128

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB n = 128
2 Correct 2 ms 468 KB n = 128
3 Correct 2 ms 424 KB n = 128
4 Correct 1 ms 468 KB n = 128
5 Correct 2 ms 468 KB n = 128
6 Correct 2 ms 468 KB n = 128
7 Correct 2 ms 428 KB n = 128
8 Correct 2 ms 468 KB n = 128
9 Correct 2 ms 468 KB n = 128
10 Correct 2 ms 424 KB n = 128
11 Correct 2 ms 468 KB n = 128
12 Correct 2 ms 468 KB n = 128
13 Correct 2 ms 424 KB n = 128
14 Correct 1 ms 468 KB n = 128
15 Correct 2 ms 468 KB n = 128