oj.uz

Submission #152846

# Submission time Handle Problem Language Result Execution time Memory
152846 2019-09-10T05:28:07 Z tri Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 4 ms 632 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = false;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

void add_element(string str);

void compile_set();

bool check_element(string str);

int N;

void add(int l, int r) {
//    ps(l, r);
    if (l == r) {
        return;
    }
    int sz = r - l + 1;
    int hf = sz / 2;

    for (int i = 0; i < hf; i++) {
        vector<char> str(N, '0');
        for (int j = 0; j < l; j++) {
            str[j] = '1';
        }
        for (int j = r + 1; j < N; j++) {
            str[j] = '1';
        }
        str[l + i] = '1';
//        ps("add:", string(str.begin(), str.end()));
        add_element(string(str.begin(), str.end()));
    }

    add(l, l + hf - 1);
    add(l + hf, r);
}

vi find(int l, int r, vi set) {
//    ps("!", l, r);
//    ps(set);
    if (l == r) {
        assert(set.size() == 1);
        return set;
    }

    int sz = r - l + 1;
    int hf = sz / 2;

    vi lSet, rSet;

    vector<char> str(N, '1');

    for (int x : set) {
        str[x] = '0';
    }

    for (int x : set) {
        str[x] = '1';
        if (check_element(string(str.begin(), str.end()))) {
            lSet.pb(x);
        } else {
            rSet.pb(x);
        }

        str[x] = '0';
    }

//    ps(lSet);
//    ps(rSet);

    assert(lSet.size() == hf);
    assert(lSet.size() + rSet.size() == sz);
    vi resL = find(l, l + hf - 1, lSet);
    vi resR = find(l + hf, r, rSet);
    resL.insert(resL.end(), resR.begin(), resR.end());
    return resL;
}

vi restore_permutation(int iN, int w, int r) {
//    ps("called");
    N = iN;
    add(0, N - 1);
//    ps("added");
    compile_set();
//    ps("compiled");
    vi tSet;
    for (int i = 0; i < N; i++) {
        tSet.pb(i);
    }
    vi res = find(0, N - 1, tSet);
//    ps(ans);
    vi ans(N);
    for (int i = 0; i < N; i++) {
        ans[res[i]] = i;
    }
    return ans;
}

Compilation message

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from messy.cpp:1:
messy.cpp: In function 'vi find(int, int, vi)':
messy.cpp:143:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(lSet.size() == hf);
            ~~~~~~~~~~~~^~~~
messy.cpp:144:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(lSet.size() + rSet.size() == sz);
            ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

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