oj.uz

Submission #721044

# Submission time Handle Problem Language Result Execution time Memory
721044 2023-04-10T08:50:20 Z yuuhi Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 3 ms 468 KB 
#include<bits/stdc++.h>
#include "messy.h"

#define f first
#define s second
#define _size(x) ((int)((x).size()))

using namespace std ;

typedef pair< long long , long long > ii ;

const int maxN = 200 + 10 ;
const int oo = 1e9 + 10 ;
mt19937 rng(time(nullptr)) ;

vector< int > restore_permutation (int n , int W , int R) {
    vector< int > st(n) ;
    iota(st.begin() , st.end() , 0) ;
    vector< int > p(n) ;

    function< void(int , int) > init = [&](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' ;
        for (int i = l ; i <= mid ; ++ i) {
            s[i] = '1' ;
            add_element(s) ;
            s[i] = '0' ;
        }
        init(l , mid) ;
        init(mid + 1 , r) ;
    };

    function< void(int , int , vector< int >) > solve = [&](int l , int r , vector< int > st) {
        if (l == r) {
            p[st[0]] = l ;
            return ;
        }

        int mid = (l + r) >> 1 ;
        string s(n , '1') ;
        for (int i : st) s[i] = '0' ;
        vector< int > lef , rig ;
        for (int i : st) {
            s[i] = '1' ;
            if (check_element(s)) lef.push_back(i) ;
            else rig.push_back(i) ;
            s[i] = '0' ;
        }

        solve(l , mid , lef) ;
        solve(mid + 1 , r , rig) ;
    };

    init(0 , n - 1) ;
    compile_set() ;
    solve(0 , n - 1 , st) ;
    return p ;
}

//int main() {
//    #define name "abc"
//    if (fopen(name".inp" , "r")) {
//        freopen(name".inp" , "r" , stdin) ;
//        freopen(name".out" , "w" , stdout) ;
//    }
//    ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
//
//    return 0 ;
//}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 8
2 Correct 1 ms 308 KB n = 8
3 Correct 1 ms 212 KB n = 8
4 Correct 1 ms 212 KB n = 8
5 Correct 1 ms 212 KB n = 8
6 Correct 1 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 212 KB n = 8
10 Correct 1 ms 212 KB n = 8
11 Correct 0 ms 212 KB n = 8
12 Correct 1 ms 300 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory 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 1 ms 212 KB n = 32
5 Correct 1 ms 212 KB n = 32
6 Correct 1 ms 300 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 304 KB n = 32
11 Correct 1 ms 212 KB n = 32
12 Correct 1 ms 300 KB n = 32
13 Correct 1 ms 212 KB n = 32
14 Correct 1 ms 212 KB n = 32
15 Correct 1 ms 212 KB n = 32

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 32
2 Correct 1 ms 304 KB n = 32
3 Correct 1 ms 212 KB n = 32
4 Correct 1 ms 212 KB n = 32
5 Correct 1 ms 304 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 300 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 212 KB n = 32
15 Correct 1 ms 212 KB n = 32

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 436 KB n = 128
2 Correct 1 ms 468 KB n = 128
3 Correct 2 ms 468 KB n = 128
4 Correct 2 ms 468 KB n = 128
5 Correct 2 ms 468 KB n = 128
6 Correct 2 ms 428 KB n = 128
7 Correct 2 ms 468 KB n = 128
8 Correct 2 ms 436 KB n = 128
9 Correct 1 ms 468 KB n = 128
10 Correct 1 ms 468 KB n = 128
11 Correct 2 ms 432 KB n = 128
12 Correct 2 ms 432 KB n = 128
13 Correct 3 ms 468 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 428 KB n = 128
2 Correct 2 ms 428 KB n = 128
3 Correct 2 ms 468 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 1 ms 468 KB n = 128
9 Correct 2 ms 468 KB n = 128
10 Correct 2 ms 468 KB n = 128
11 Correct 2 ms 428 KB n = 128
12 Correct 2 ms 468 KB n = 128
13 Correct 2 ms 468 KB n = 128
14 Correct 2 ms 468 KB n = 128
15 Correct 2 ms 468 KB n = 128