Submission #750990

#	Time	Username	Problem	Language	Result	Execution time	Memory
750990		puppy	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	2 ms	496 KiB

messy

#include <vector>
#include <iostream>
#include <string>
#include "messy.h"
using namespace std;
int N;
void push(int s, int e)
{
    if (s == e) return;
    int m = s + e >> 1;
    string st(N, '1');
    for (int i = s; i <= e; i++) st[i] = '0';
    for (int i = s; i <= m; i++) {
        st[i] = '1';
        add_element(st);
        st[i] = '0';
    }
    push(s, m);
    push(m+1, e);
}
vector<int> p;
void dnc(int s, int e, vector<int> v)
{
    if (s == e) {
        p[v[0]] = s;
        return;
    }
    int m = s + e >> 1;
    vector<int> v1, v2;
    string st(N, '1');
    for (int i:v) st[i] = '0';
    for (int i:v) {
        st[i] = '1';
        if (check_element(st)) v1.push_back(i);
        else v2.push_back(i);
        st[i] = '0';
    }
    dnc(s, m, v1);
    dnc(m+1, e, v2);
}
std::vector<int> restore_permutation(int n, int w, int r) {
    N = n;
    p.resize(N);
    push(0, N-1);
    vector<int> v(N);
    for (int i = 0; i < N; i++) v[i] = i;
    compile_set();
    dnc(0, N-1, v);
    return p;
}

Compilation message (stderr)

messy.cpp: In function 'void push(int, int)':
messy.cpp:10:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 |     int m = s + e >> 1;
      |             ~~^~~
messy.cpp: In function 'void dnc(int, int, std::vector<int>)':
messy.cpp:28:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |     int m = s + e >> 1;
      |             ~~^~~

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