oj.uz

Submission #586184

# Submission time Handle Problem Language Result Execution time Memory
586184 2022-06-30T03:53:15 Z Do_you_copy Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 3 ms 468 KB 
#include <bits/stdc++.h>
#include <messy.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

using ll = long long;
using pii = pair <int, int>;

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

const ll Mod = 1000000007;
const int maxN = 1e5 + 1;
int n;
int a[128];
int hiddenarray[] = {3, 1, 7, 4, 5, 0, 6, 2};
vector <string> v;

struct TNode{
    vector <int> q;
};
/*
void add_element(string s){
    v.pb(s);
}

void compile_set(){
    for (string &t: v){
        string tt = t;
        for (int i = 0; i < n; ++i){
            tt[i] = t[hiddenarray[i]];
        }
        t = tt;
    }
}

bool check_element(string s){
    for (string t: v){
        if (s == t) return 1;
    }
    return 0;
}*/

void dnc(int l, int r){
    if (l == r) return;
    int m = (l + r) / 2;
    string s = "";
    for (int i = 1; i < l; ++i) s += '1';
    for (int i = l; i <= r; ++i) s += '0';
    for (int i = r + 1; i <= n; ++i) s += '1';
    for (int i = l; i <= m; ++i){
        s[i - 1] = '1';
        add_element(s);
        s[i - 1] = '0';
    }
    dnc(l, m);
    dnc(m + 1, r);
}

void dncreturnans(int l, int r, string s){
    vector <int> left, right;
    for (int i = 0; i < n; ++i){
        if (s[i] == '0'){
            s[i] = '1';
            if (check_element(s)){
                left.pb(i);
            }
            else right.pb(i);
            s[i] = '0';
        }
    }
    if (r - l == 1){
        a[left[0]] = l - 1;
        a[right[0]] = r - 1;
        return;
    }
    int m = (l + r) / 2;
    for (int i: right) s[i] = '1';
    dncreturnans(l, m, s);
    for (int i: right) s[i] = '0';
    for (int i: left) s[i] = '1';
    dncreturnans(m + 1, r, s);
}

vector <int> restore_permutation(int N, int w, int r){
    n = N;
    vector <int> b;
    dnc(1, n);
    compile_set();
    string s;
    for (int i = 1; i <= n; ++i) s += '0';
    dncreturnans(1, n, s);
    for (int i = 0; i < n; ++i) b.pb(a[i]);
    return b;
}

Subtask #1
20.0 / 20.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 32
2 Correct 0 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 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 216 KB n = 32
10 Correct 1 ms 212 KB n = 32
11 Correct 1 ms 212 KB n = 32
12 Correct 0 ms 296 KB n = 32
13 Correct 1 ms 212 KB n = 32
14 Correct 1 ms 212 KB n = 32
15 Correct 1 ms 300 KB n = 32

Subtask #4
21.0 / 21.0

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