Submission #484015

#	Time	Username	Problem	Language	Result	Execution time	Memory
484015		gmyu	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	3 ms	460 KiB

messy

/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/IOI16_messy
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <string.h>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define ff  first
#define ss  second
#define pb  push_back
#define sz(x)   (int)(x).size()

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 300007
#define MAXE 100007

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
    int x, y;
    int val;
    int visited;
    bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
    int from, to;
    ll weight;
    bool operator<(EDGE other) const { return weight < other.weight; }
};

bool debug=false;

/** use divide and conquer
 *  we add elements the region of interest is 0. For the first half of this region, we flip 0 -> 1 one at a time
 *  then we do the check, we binary check whether that elements is in the left or right
 */
#include "messy.h"
vi p;

void dnc_add(int l, int r, int n){
    if (l>r) return;
    if (l==r) return;

    if(debug) cout << "range " << l << " - " << r << endl;
    string s = "";
    for (int i=0;i<n;i++)
        s += (l<=i && i <=r) ? "0" : "1";

    int m = (l+r)/2;
    for (int i=l;i<=m;i++){  //
        s[i] = '1';
        add_element(s);
        if(debug) cout << "  .. add " << s << endl;
        s[i] = '0';
    }
    dnc_add(l, m, n); dnc_add(m+1, r, n);
}

void dnc_check(int l, int r, int n, vi plist){
    if(plist.empty()) return;
    if(l>r) return;

    if(debug) {
        cout << "search range " << l << " - " << r << endl << "  ";
        for(auto i : plist) cout << i << " ";
        cout << endl;
    }

    if (l==r){
        p[plist[0]] = l; return;
    }

    string s(n, '1');
    for (auto i : plist) s[i] = '0';

    vector<int> L, R;
    L.clear(); R.clear();
    for (auto i : plist){
        s[i] = '1';
        if (check_element(s)) L.pb(i);
        else R.pb(i);
        s[i] = '0';
    }

    int m = (l+r)/2;
    dnc_check(l, m, n, L); dnc_check(m+1, r, n, R);
}

vi restore_permutation(int n, int w, int r) {
    p.resize(n);
    dnc_add(0, n-1, n);
    compile_set();

    if(debug) cout << "now find p" << endl;
    vi idx;
    for (int i=0;i<n;i++) idx.pb(i);
    dnc_check(0, n-1, n, idx);

    return p;
}

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