Submission #542830

#	Time	Username	Problem	Language	Result	Execution time	Memory
542830		alextodoran	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	3 ms	468 KiB

messy

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void add_element (string x);
bool check_element (string x);
void compile_set ();

void addAll (vector <int> a, string A) {
    if ((int) a.size() == 1) {
        return;
    }
    int mid = (int) a.size() / 2;
    vector <int> al, ar;
    for (int i = 0; i < mid; i++) {
        al.push_back(a[i]);
    }
    for (int i = mid; i < (int) a.size(); i++) {
        ar.push_back(a[i]);
    }
    for (int i : al) {
        A[i] = '1';
        add_element(A);
        A[i] = '0';
    }
    string Al = A, Ar = A;
    for (int i : al) {
        Ar[i] = '1';
    }
    for (int i : ar) {
        Al[i] = '1';
    }
    addAll(al, Al);
    addAll(ar, Ar);
}

vector <int> sol;

void getAll (vector <int> b, string B) {
    if ((int) b.size() == 1) {
        sol.push_back(b[0]);
        return;
    }
    int mid = (int) b.size() / 2;
    vector <int> bl, br;
    for (int i : b) {
        B[i] = '1';
        if (check_element(B) == true) {
            bl.push_back(i);
        } else {
            br.push_back(i);
        }
        B[i] = '0';
    }
    string Bl = B, Br = B;
    for (int i : bl) {
        Br[i] = '1';
    }
    for (int i : br) {
        Bl[i] = '1';
    }
    getAll(bl, Bl);
    getAll(br, Br);
}

vector <int> restore_permutation (int n, int w, int r) {
    string X(n, '0');
    vector <int> x(n);
    iota(x.begin(), x.end(), 0);
    addAll(x, X);
    compile_set();
    getAll(x, X);
    vector <int> ans(n);
    for (int i = 0; i < n; i++) {
        ans[sol[i]] = i;
    }
    return ans;
}

Compilation message (stderr)

messy.cpp: In function 'void getAll(std::vector<int>, std::string)':
messy.cpp:54:9: warning: unused variable 'mid' [-Wunused-variable]
   54 |     int mid = (int) b.size() / 2;
      |         ^~~

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