Submission #1019147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019147		ProtonDecay314	Unscrambling a Messy Bug (IOI16_messy)	C++17	38 / 100	1 ms	436 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_pc1(n, false);
    int pc1mask = 0;
    LI(j, 0, n) {
        if(check_element(to_binstring(1 << j, n))) {
            is_pc1[j] = true;
            pc1mask |= 1 << j;
        }
    }

    vi found(n, false);
    
    int first_left_bit;
    LI(j, 0, n) {
        if(is_pc1[j] && check_element(to_binstring(pc1mask ^ (1 << j), n))) {
            first_left_bit = j;
            ans[j] = 0;
            found[j] = true;
            break;
        }
    }

    int cur_left_mask = pc1mask ^ (1 << first_left_bit);

    LI(i, 1, n >> 1) {
        LI(j, 0, n >> 1) {
            if(is_pc1[j] && !found[j]) {
                if(check_element(to_binstring(cur_left_mask ^ (1 << j), n))) {
                    ans[j] = i;
                    found[j] = true;
                    cur_left_mask = ~(1 << j);
                }
            }
        }
    }

    // Right bit
    int first_right_bit;
    LI(j, 0, n) {
        if(!is_pc1[j] && check_element(to_binstring((~pc1mask) ^ (1 << j), n))) {
            first_right_bit = j;
            ans[j] = 0;
            found[j] = true;
            break;
        }
    }

    int cur_right_mask = pc1mask ^ (1 << first_left_bit);

    LI(i, 1, n >> 1) {
        LI(j, 0, n >> 1) {
            if(!is_pc1[j] && !found[j]) {
                if(check_element(to_binstring(cur_right_mask ^ (1 << j), n))) {
                    ans[j] = i;
                    found[j] = true;
                    cur_right_mask = ~(1 << j);
                }
            }
        }
    }

    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

Compilation message (stderr)

messy.cpp: In function 'vi subtask3(int, int, int)':
messy.cpp:120:9: warning: unused variable 'cur_mask' [-Wunused-variable]
  120 |     int cur_mask = 0;
      |         ^~~~~~~~
messy.cpp:161:9: warning: variable 'first_right_bit' set but not used [-Wunused-but-set-variable]
  161 |     int first_right_bit;
      |         ^~~~~~~~~~~~~~~
messy.cpp:146:38: warning: 'first_left_bit' may be used uninitialized in this function [-Wmaybe-uninitialized]
  146 |     int cur_left_mask = pc1mask ^ (1 << first_left_bit);
      |                                   ~~~^~~~~~~~~~~~~~~~~~

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