Submission #394146

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

messy

// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef arwaeystoamneg
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
#endif
}
#ifndef arwaeystoamneg
#include "messy.h"
#endif
#ifdef arwaeystoamneg

namespace helper {

    set<string> set_;
    bool compiled = false;
    int N;
    vector<int> p;
    int w;
    int r;

    int read_int() {
        int x;
        cin >> x;
        return x;
    }

}

using namespace helper;


// A convenience function.
int get_p(int i) {
    int ret = p[i];
    return ret;
}
void wa() {
    printf("WA\n");
    exit(0);
}

bool check(const string& x) {
    if ((int)x.length() != N) {
        return false;
    }
    for (int i = 0; i < N; i++) {
        if (x[i] != '0' && x[i] != '1') {
            return false;
        }
    }
    return true;
}
void add_element(string x) {
    cout << x << endl;
    if (--w < 0 || compiled || !check(x)) {
        wa();
    }
    set_.insert(x);
}

bool check_element(string x) {
    if (--r < 0 || !compiled || !check(x)) {
        wa();
    }
    return set_.count(x);
}

void compile_set() {
    if (compiled) {
        wa();
    }
    compiled = true;
    set<string> compiledSet;
    string compiledElement = string(N, ' ');
    for (set<string>::iterator it = set_.begin(); it != set_.end(); it++) {
        string s = *it;
        for (int i = 0; i < N; i++) {
            compiledElement[i] = s[get_p(i)];
        }
        compiledSet.insert(compiledElement);
    }
    set_ = compiledSet;
}
#endif
int n, SZ;
void build(int l, int r)
{
    if (l == r)
    {
        return;
    }
    string init = "";
    F0R(j, l)
    {
        init.pb('1');
    }
    FOR(j, l, r + 1)init.pb('0');
    FOR(j, r + 1, n)
    {
        init.pb('1');
    }
    int m = (l + r) / 2;
    FOR(i, l, m + 1)
    {
        init[i] = '1';
        add_element(init);
        init[i] = '0';
    }
    build(m + 1, r);
    build(l, m);
}
vi ans;
void solve(int l, int r, vector<int>&in)
{
    if (l == r)
    {
        assert(sz(in) == 1);
        ans[l] = *in.begin();
        return;
    }
    string c = "";
    F0R(i, n)c.pb('1');
    trav(x, in)c[x] = '0';
    int m = (l + r) / 2;
    vector<int>t1, t2;
    F0R(i, n)
    {
       if (c[i] == '0')
       {
           c[i] = '1';
           int res = check_element(c);
           if (res)
           {
               t1.pb(i);
           }
           else
           {
               t2.pb(i);
           }
           c[i] = '0';
       }
    }
    solve(l, m, t1);
    solve(m + 1, r, t2);
}
std::vector<int> restore_permutation(int N, int w, int r) 
{
    n = N;
    SZ = log2(n);
    build(0, n - 1);
    compile_set();
    vector<int>in;
    F0R(i, n)in.pb(i);
    ans.rsz(n);
    solve(0, n - 1, in);
    vi t(n);
    F0R(i, n)t[ans[i]] = i;
    return t;
}


#ifdef arwaeystoamneg

int main() {
    setIO("test1");
    N = read_int();
    w = read_int();
    r = read_int();
    p = vector<int>(N);
    for (int i = 0; i < N; i++) {
        p[i] = read_int();
    }
    vector<int> answer = restore_permutation(N, w, r);

    if (answer.size() != N) {
        printf("WA\n");
        return 0;
    }


    printf("%d", answer[0]);

    for (int i = 1; i < N; i++) {
        printf(" %d", answer[i]);
    }
    printf("\n");
    return 0;
}



#endif

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