Submission #697065

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

messy

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T>
ostream& operator<<(ostream& os, const set<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(x, y) uniform_int_distribution<int>(x, y)(rng)

void wa();
bool check(const string& x);
void add_element(string x);
bool check_element(string x);
void compile_set();

ll mod(ll a, ll b) { return ((a%b) + b) % b; }
ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    ll g = a; x = 1, y = 0;
    if(b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
    return g;
}
ll inv(ll a, ll m) {
    ll x, y; ll g = ext_gcd(a, m, x, y);
    if(g > 1) return -1;
    return mod(x, m);
}
int N;
string to_string(int s, int e){
    string re = "";
    for(int i=0; i<N; i++)
        re.append((i>=s&&i<=e)?"0":"1");
    return re;
}
void build(int s, int e){
    string base = to_string(s, e);
    if(s==e)
        return;
    int m = (s+e)/2;
    for (int i=s;i<=m;i++){
        base[i] = '1';
        add_element(base);
        base[i] = '0';
    }
    build(s, m);
    build(m+1, e);
}
vector <int> dap;
void solve(int s, int e, set <int> now){
//    cout << "solve (" << s << ", " << e << ") : " << now << "\n";
    if(s==e){
        dap[*(now.begin())]=s;
        return;
    }
    int mid = (s+e)/2;
    set <int> left, right;
    string base;
    for(int i=0;i<N;i++)
        base.append((now.find(i)!=now.end())?"0":"1");
    for(int i:now){
        base[i] = '1';
        if(check_element(base))
            left.insert(i);
        else
            right.insert(i);
        base[i] = '0';
    }
    solve(s, mid, left);
    solve(mid+1, e, right);
}

std::vector<int> restore_permutation(int n, int w, int r) {
    N = n;
    build(0, n-1);
    compile_set();
    dap.resize(n);
    set <int> now;
    for(int i=0;i<n;i++)
        now.insert(i);
    solve(0, n-1, now);
    return dap;
}

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