oj.uz

Submission #1019965

# Submission time Handle Problem Language Result Execution time Memory
1019965 2024-07-11T11:23:58 Z ProtonDecay314 Unscrambling a Messy Bug (IOI16_messy) C++17
100 / 100
 2 ms 636 KB 
// AM+DG

/*

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<bool> vb;
#define L(i, varmn, varmx) for(ll i = varmn; i < varmx; i++)
#define LR(i, varmx, varmn) for(ll i = varmx; i > varmn; i--)
#define LI(i, varmn, varmx) for(int i = varmn; i < varmx; i++)
#define LIR(i, varmx, varmn) for(int i = varmx; i > varmn; i--)
#define pb push_back
#include "messy.h"

void write(int orig_n, int n, int l, int r) {
    string cur_mask(orig_n, '1');

    LI(i, l, r + 1) {
        cur_mask[i] = '0';
    }

    string to_push;
    LI(i, 0, n >> 1) {
        to_push = cur_mask;
        to_push[i + l] = '1';

        add_element(to_push);
    }

    if(n > 2) {
        int m = (l + r) >> 1;
        write(orig_n, n >> 1, l, m);
        write(orig_n, n >> 1, m + 1, r); // This is starting to look like segtree code LOL
    }
}

void solve(int orig_n, int n, int offset, const set<int>& inds, vi& ans) {
    set<int> left;
    set<int> right;

    string base_mask(orig_n, '1');
    for(int i : inds) {
        base_mask[i] = '0';
    }

    string cur_mask;
    
    for(int i : inds) {
        cur_mask = base_mask;
        cur_mask[i] = '1';

        (check_element(cur_mask) ? left : right).insert(i);        
    }

    if(n > 2) {
        solve(orig_n, n >> 1, offset, left, ans);
        solve(orig_n, n >> 1, offset + (n >> 1), right, ans);
    } else {
        // cout << "KIMI DAYO KIMI NANDAYO " << *(left.begin()) << " " << *(right.begin()) << endl;
        // (If you're reading this, I was listening to YLIA OST while coding so yeah, haha)

        // The thing in the left set is index offset
        ans[*(left.begin())] = offset;

        // The thing in the right set is index offset + (n >> 1)
        ans[*(right.begin())] = offset + (n >> 1);
    }
}

vi restore_permutation(int n, int w, int r) {
    
    // Write Elements
    write(n, n, 0, n - 1);

    // Compile the set!
    compile_set();

    // Solve!
    vi ans(n, -1);
    set<int> inds;
    LI(i, 0, n) inds.insert(i);
    solve(n, n, 0, inds, ans);

    // LI(i, 0, n) {
    //     cout << ans[i] << " ";
    // }
    // cout << endl;

    return ans;
}

#ifdef DEBUG
int main() {

}
#endif

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

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