Submission #1019138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019138		ProtonDecay314	Unscrambling a Messy Bug (IOI16_messy)	C++17	38 / 100	1 ms	440 KiB

messy

// 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;
#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"

// #define DEBUG

string to_binstring(int num, int n) {
    string res;

    LI(i, 0, n) {
        res.pb(((num >> i) & 0b1 ? '1' : '0'));
    }

    assert((int)res.size() == n);

    return res;
}

vi subtasks12(int n, int w, int r) {
    LI(i, 0, n + 1) {
        // Construct a string with this many zeros
        string elem;
        LI(j, 0, i) {
            elem.pb('1');
        }

        LI(j, i, n) {
            elem.pb('0');
        }

        add_element(elem);
    }


    compile_set();

    int cur_mask = 0;

    vi ans(n, 0);

    LI(i, 0, n) {
        LI(j, 0, n) {
            if(((cur_mask >> j) & 0b1) == 0) {
                if(check_element(to_binstring(cur_mask | (1 << j), n))) {
                    // We found the next bitpos
                    cur_mask |= (1 << j);

                    ans[j] = i;
                    break;
                }
            }
        }
    }
    return ans;
}

// vi subtask3(int n, int w, int r) {
//     // Meet in the middle
//     LI(i, 1, (n >> 1) + 1) {
//         string elem;
//         LI(j, 0, i - 1) {
//             elem.pb('0');
//         }
//         elem.pb('1');

//         LI(j, i, n) {
//             elem.pb('0');
//         }

//         add_element(elem);
//     }

//     LI(i, 0, (n >> 1)) {
//         string elem(n, '1');
//         LI(j, n >> 1, n) {
//             elem[j] = '0';
//         }

//         elem[i] = '0';

//         if(i > 0) elem[i - 1] = '0';

//         add_element(elem);
//     }

//     LI(i, 0, (n >> 1)) {
//         string elem(n, '1');
//         LI(j, 0, n >> 1) {
//             elem[j] = '0';
//         }

//         elem[i + (n >> 1)] = '0';

//         if(i > 0) elem[i + (n >> 1) - 1] = '0';

//         add_element(elem);
//     }

//     compile_set();

//     int cur_mask = 0;

//     vi ans(n, 0);

//     // Iterate, finding the ones with popcount 1
//     vi is_popcount_1;
//     LI(j, 0, n) {
//         if(check_element(to_binstring(1 << j)))
//     }

//     // LI(i, 0, n) {
//     //     LI(j, 0, n) {
//     //         if(((cur_mask >> j) & 0b1) == 0) {
//     //             if(check_element(to_binstring(cur_mask | (1 << j), n))) {
//     //                 // We found the next bitpos
//     //                 cur_mask |= (1 << j);

//     //                 ans[n - j - 1] = i;
//     //                 break;
//     //             }
//     //         }
//     //     }
//     // }

//     return ans;
// }

vi restore_permutation(int n, int w, int r) {
    if((n == 8 && w == 256 && r == 256) || (n == 32 && w == 320 && r == 1024)) return subtasks12(n, w, r);
    // else if(n == 32 & w == 1024 && r == 320) return subtask3(n, w, r);

    vi nope;
    return nope;
}

#ifdef DEBUG
int main() {

}
#endif

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 0 / 11
• Subtask 4: 0 / 21
• Subtask 5: 0 / 30