oj.uz

Submission #66349

# Submission time Handle Problem Language Result Execution time Memory
66349 2018-08-10T09:35:07 Z aquablitz11 Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 4 ms 512 KB 
#include <bits/stdc++.h>
#include "messy.h"
using namespace std;

using pii = pair<int, int>;
const int N = 128;
const int LN = 7;

int n, ln, ans[N][LN]; // 1 = left, 0 = right

string construct(int l, int r, int ca)
{
    string s(n, '0');
    for (int i = 0; i < l; ++i)
        s[i] = i < ca ? '1' : '0';
    for (int i = n-1; i > r; --i)
        s[i] = '1';
    return s;
}

void build_tree(int l, int r, int ca)
{
    if (l == r) return;
    string s = construct(l, r, ca);
    int m = (l+r)/2;
    for (int i = l; i <= m; ++i) {
        string t(s);
        t[i] = '1';
        add_element(t);
    }
    build_tree(l, m, ca);
    build_tree(m+1, r, ca+1);
}

pii getrange(int i)
{
    int l = 0, r = n-1;
    for (int j = 0; j < ln; ++j) {
        if (ans[i][j] == -1) break;
        int m = (l+r)/2;
        if (ans[i][j] == 1) r = m;
        else l = m+1;
    }
    return pii(l, r);
}

void query_tree(int l, int r, int ca, int dep)
{
    if (l == r) return;
    string s = construct(l, r, ca);
    string q(n, '0');
    for (int i = 0; i < n; ++i) {
        pii ri = getrange(i);
        if (ri != pii(l, r))
            q[i] = s[ri.first];
    }
    for (int i = 0; i < n; ++i) {
        pii ri = getrange(i);
        if (ri == pii(l, r)) {
            string t(q);
            t[i] = '1';
            bool ret = check_element(t);
            ans[i][dep] = ret?1:0;
        }
    }
    int m = (l+r)/2;
    query_tree(l, m, ca, dep+1);
    query_tree(m+1, r, ca+1, dep+1);
}

vector<int> restore_permutation(int n, int w, int r)
{
    ::n = n;
    ln = 0;
    while ((1<<ln) < n) ++ln;
    for (int i = 0; i < n; ++i) for (int j = 0; j < ln; ++j)
        ans[i][j] = -1;
    build_tree(0, n-1, 0);
    compile_set();
    query_tree(0, n-1, 0, 0);

    vector<int> ans;
    for (int i = 0; i < n; ++i)
        ans.push_back(getrange(i).first);
    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 8
2 Correct 2 ms 256 KB n = 8
3 Correct 2 ms 256 KB n = 8
4 Correct 2 ms 256 KB n = 8
5 Correct 2 ms 384 KB n = 8
6 Correct 2 ms 256 KB n = 8
7 Correct 2 ms 256 KB n = 8
8 Correct 2 ms 384 KB n = 8
9 Correct 2 ms 384 KB n = 8
10 Correct 2 ms 384 KB n = 8
11 Correct 2 ms 256 KB n = 8
12 Correct 2 ms 512 KB n = 8
13 Correct 2 ms 384 KB n = 8
14 Correct 2 ms 384 KB n = 8
15 Correct 3 ms 384 KB n = 8

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 32
2 Correct 2 ms 384 KB n = 32
3 Correct 2 ms 384 KB n = 32
4 Correct 2 ms 384 KB n = 32
5 Correct 2 ms 384 KB n = 32
6 Correct 2 ms 384 KB n = 32
7 Correct 2 ms 384 KB n = 32
8 Correct 2 ms 384 KB n = 32
9 Correct 2 ms 384 KB n = 32
10 Correct 2 ms 384 KB n = 32
11 Correct 2 ms 384 KB n = 32
12 Correct 2 ms 384 KB n = 32
13 Correct 2 ms 384 KB n = 32
14 Correct 2 ms 384 KB n = 32
15 Correct 2 ms 384 KB n = 32

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 32
2 Correct 2 ms 384 KB n = 32
3 Correct 2 ms 384 KB n = 32
4 Correct 2 ms 384 KB n = 32
5 Correct 2 ms 384 KB n = 32
6 Correct 2 ms 384 KB n = 32
7 Correct 2 ms 384 KB n = 32
8 Correct 2 ms 384 KB n = 32
9 Correct 3 ms 384 KB n = 32
10 Correct 2 ms 384 KB n = 32
11 Correct 2 ms 384 KB n = 32
12 Correct 3 ms 384 KB n = 32
13 Correct 2 ms 384 KB n = 32
14 Correct 2 ms 384 KB n = 32
15 Correct 2 ms 384 KB n = 32

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB n = 128
2 Correct 4 ms 512 KB n = 128
3 Correct 4 ms 512 KB n = 128
4 Correct 4 ms 512 KB n = 128
5 Correct 3 ms 512 KB n = 128
6 Correct 4 ms 512 KB n = 128
7 Correct 4 ms 512 KB n = 128
8 Correct 4 ms 512 KB n = 128
9 Correct 4 ms 512 KB n = 128
10 Correct 3 ms 512 KB n = 128
11 Correct 4 ms 512 KB n = 128
12 Correct 4 ms 512 KB n = 128
13 Correct 4 ms 512 KB n = 128
14 Correct 4 ms 512 KB n = 128
15 Correct 4 ms 512 KB n = 128

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB n = 128
2 Correct 3 ms 512 KB n = 128
3 Correct 3 ms 512 KB n = 128
4 Correct 4 ms 512 KB n = 128
5 Correct 4 ms 512 KB n = 128
6 Correct 4 ms 512 KB n = 128
7 Correct 4 ms 512 KB n = 128
8 Correct 3 ms 512 KB n = 128
9 Correct 3 ms 512 KB n = 128
10 Correct 4 ms 512 KB n = 128
11 Correct 4 ms 512 KB n = 128
12 Correct 4 ms 512 KB n = 128
13 Correct 4 ms 512 KB n = 128
14 Correct 4 ms 512 KB n = 128
15 Correct 3 ms 512 KB n = 128