Submission #143809

#	Time	Username	Problem	Language	Result	Execution time	Memory
143809		dacin21	Split the Attractions (IOI19_split)	C++14	40 / 100	1958 ms	17156 KiB

split

#include "split.h"


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

using ll = long long;
using ull = unsigned long long;
using fl = long double;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename S, typename T>
void xmin(S&a, T const&b){if(b<a) a=b;}
template<typename S, typename T>
void xmax(S&a, T const&b){if(b>a) a=b;}

template<bool enabled>
struct Debug{
    template<typename S, typename T = void> struct Tag_Printable : false_type {};
    template<typename S> struct Tag_Printable<S, decltype((void)(cerr << declval<S>()))> : true_type {};
    template<typename S, typename T = void> struct Tag_Iterable: false_type {};
    template<typename S> struct Tag_Iterable<S, decltype((void)(begin(declval<S>()), end(declval<S>())))> : true_type {};

    template<typename T, size_t N> struct Tuple_Printer{
        template<typename S>
        static S& print(S& stream, T const&t){
            return Tuple_Printer<T, N-1>::print(stream, t) << ", " << get<N>(t);
        }
    };
    template<typename T> struct Tuple_Printer<T, 0>{
        template<typename S>
        static S& print(S& stream, T const&t){
            return stream << get<0>(t);
        }
    };

    template<typename T, typename... Args>
    Debug& print(T const&x, true_type, Args...){
        #ifdef LOCAL_RUN
        if(enabled){
            cerr << boolalpha << x;
        }
        #endif // LOCAL_RUN
        return *this;
    }
    template<typename T>
    Debug& print(T const&x, false_type, true_type){
        *this << "[";
        bool first = true;
        for(auto &e:x){
            if(!first) *this << ", ";
            *this << e;
            first = false;
        }
        return *this << "]";
    }
    template<typename S, typename T>
    Debug& print(pair<S, T> const&x, false_type, false_type){
        return *this << "(" << x.first << ", " << x.second << ")";
    }
    template<typename... Args>
    Debug& print(tuple<Args...> const&t, false_type, false_type){
        return Tuple_Printer<decltype(t), sizeof...(Args)-1>::print(*this, t);
    }
    template<typename T>
    Debug& operator<<(T const&x){
        return print(x, Tag_Printable<T>{}, Tag_Iterable<T>{});
    }
};
 Debug<true> debug;
// Debug<false> debug; // disable debug printing
#define named(x) string(#x) << " : " <<  x


int n, a, b, c;
vector<bool> vis;
vector<vector<int> > g;

vector<int> L, R, deco;
vector<int> siz;
int tim;


int dfs(int u){
    assert(!vis[u]);
    vis[u] = 1;
    siz[u] = 1;
    L[u] = ++tim;
    deco[L[u]] = u;
    int ret = -1;
    for(auto const&e:g[u]){
        if(!vis[e]){
            const int tmp = dfs(e);
            if(tmp>=0) ret = tmp;
            siz[u]+=siz[e];
        }
    }
    R[u] = tim;
    if(a <= siz[u] && siz[u] <= n-b) ret = u;
    return ret;
}

mt19937 rng(4353215);
vector<int> find_split(int n_, int a_, int b_, int c_, vector<int> p, vector<int> q) {
    n=n_;
    array<int, 3> pool{a_, b_, c_};
    array<int, 3> label{1,2,3};
    auto start = clock();
    while((clock()-start)*1.0/CLOCKS_PER_SEC < 1.8){
        do{
            a = pool[label[0]-1];
            b = pool[label[1]-1];
            c = pool[label[2]-1];

            g.assign(n, decltype(g)::value_type{});
            for(int i=0;i<(int)p.size();++i){
                auto const e = p[i], f = q[i];
                g[e].emplace_back(f);
                g[f].emplace_back(e);
            }
            for(auto &e:g) shuffle(e.begin(), e.end(), rng);
            vis.assign(n, false);
            tim=-1;
            L.resize(n);
            R.resize(n);
            siz.resize(n);
            deco.resize(n);

            int tmp = dfs(uniform_int_distribution<int>(0, n-1)(rng));
            if(tmp == -1){
                continue;
            }
            // reconstruct
            vector<int> ret(n, label[2]);
            const int X = L[tmp], Y = R[tmp];
            for(int i=0;i<a;++i){
                ret[deco[X+i]] = label[0];
            }
            for(int i=0, j=0;i<b;++j){
                if(j<X || j>Y){
                    ret[deco[j]] = label[1];
                    ++i;
                }
            }
            assert(count(ret.begin(), ret.end(), label[0]) == a);
            assert(count(ret.begin(), ret.end(), label[1]) == b);
            assert(count(ret.begin(), ret.end(), label[2]) == c);
            return ret;
        } while(next_permutation(label.begin(), label.end()));
    }
    return vector<int>(n, 0);

}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36