Submission #1303174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303174		hssaan_arif	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	2 ms	584 KiB

messy

#include "messy.h"
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define pb push_back
// #define int long long
#define fi first
#define se second

const int N = 3e5 + 5, M = 1e9 + 7, LG = 20;

int n , A[N] , w , r;
vector<int> P;

void add(int se , int e , string s){

    if (se + 1 == e){
        return;
    }

    for (int i=0 ; i<n ; i++){
        if (se <= i && i < e){
            s[i] = '0';
        }else{
            s[i] = '1';
        }
    }

    int mid = (e-se)/2;

    for (int i=0 ; i<n ; i++){
        if (!mid) break;

        if (s[i] == '0'){
            s[i] = '1';
            add_element(s);
            s[i] = '0';
            mid--;
        }
    }

    mid = (se+e)/2;

    add(se , mid , s);
    add(mid , e , s);
}

void get(int se , int e , string s){

    if (se + 1 == e){
        for (int i=0 ; i<n ; i++){
            if (s[i] == '0'){
                P[i] = se;
                return;
            }
        }
    }

    int mid = (e-se)/2;

    vector<int> lc , rc;

    for (int i=0 ; i<n ; i++){
        if (s[i] == '0'){
            s[i] = '1';

            bool x = check_element(s);
            

            if (x){
                lc.pb(i);
            }else{
                rc.pb(i);
            }

            s[i] = '0';
        }
    }

    mid = (se+e)/2;
    
    for (int i : rc){
        s[i] = '1';
    }

    get(se , mid , s);

    for (int i : rc){
        s[i] = '0';
    }

    for (int i : lc){
        s[i] = '1';
    }

    get(mid , e , s);
}

vector<int> restore_permutation(int N, int w, int r) {
    n = N;
    P.resize(n , 0);
    string s = "" , t = "";
    for (int i=0 ; i<n ; i++){
        s += '0';
        t += '0';
    }
    add(0 , n , s);
    compile_set();
    get(0 , n , t);
    return P;    
}

// signed main(){
//     cin >> n >> w >> r;
//     restore_permutation(n,w,r);
// }

Compilation message (stderr)

messy.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
messy_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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