Submission #128965

#	Time	Username	Problem	Language	Result	Execution time	Memory
128965		I_Hate_AHDPIYKO	ICC (CEOI16_icc)	C++17	0 / 100	42 ms	504 KiB

icc

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define lll __int128
#define ull unsigned long long
#define fi first
#define se second
#define db double
#define ld long double
#define lld __float128

/// order_of_key, find_by_order

template<class T, class COMP>
using custom_set = tree<T, null_type, COMP, rb_tree_tag, tree_order_statistics_node_update>;

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<class T, class U>
using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd_64(chrono::steady_clock::now().time_since_epoch().count());

#include "icc.h"
//
//int query(int size_a, int size_b, int a[], int b[])
//{
//    for(int i = 0; i < size_a; i++)
//    {
//        cout << a[i] << ' ';
//    } cout << '\n';
//    for(int i = 0; i < size_b; i++)
//    {
//        cout << b[i] << ' ';
//    } cout << '\n';
//    int res; cin >> res; return res;
//}
//
//void setRoad(int a, int b)
//{
//    cout << a << " - " << b << '\n';
//}


int qrr(set<int> a, set<int> b)
{
    int n = a.size(), m = b.size();
    int A[n], B[m], i = 0;
    for(auto j : a)
    {
        A[i++] = j+1;
    }
    i = 0;
    for(auto j : b)
    {
        B[i++] = j+1;
    }
//    if(!n || !m)
//        return 0;
    return query(n, m, A, B);
}


const int MAXN = 105;

int pr[MAXN], sz[MAXN], cur;

vector<int> lc[MAXN], rc[MAXN], ind[MAXN];
vector<pair<int, int> > dat;

void solve(int l, int r, int d)
{
    if(l > r)
        return;
    int m = (l+r) / 2;

    ind[d].push_back(cur);
    int m1 = m, m2 = m;
    while(m2 < r && dat[m2].fi == dat[m].fi) m2++;
    while(m1 >= l && dat[m1].fi == dat[m+1].fi) m1--;
    if(m1+1 == l && m2 == r)
    {
        cur++;
        return;
    }
    if(m1+1 != l)
        m = m1;
    else
        m = m2;
    lc[cur].clear();
    rc[cur].clear();
    for(int i = l; i <= m; i++)
    {
        lc[cur].push_back(dat[i].se);
    }
    for(int i = m+1; i <= r; i++)
    {
        rc[cur].push_back(dat[i].se);
    }
    cur++;
    if(l == r)
        return;
    solve(l, m, d+1);
    solve(m+1, r, d+1);
}

int lead(int v)
{
    if(v == pr[v])
        return v;
    return pr[v] = lead(pr[v]);
}

bool comb(int a, int b)
{
    a = lead(a);
    b = lead(b);
    if(a == b)
        return 0;
    if(sz[a] > sz[b])
        swap(a, b);
    sz[b] += sz[a];
    pr[a] = b;
    return 1;
}



void run(int n)
{
    for(int i = 0; i < n; i++)
    {
        pr[i] = i;
        sz[i] = 1;
    }
    for(int i = 0; i < n-1; i++)
    {
        for(int j = 0; j < n; j++)
        {
            dat.push_back({lead(j), j});
            ind[j].clear();
        }
        sort(dat.begin(), dat.end());
//        for(int j = 0; j < n; j++)
//        {
//            cout << dat[j].se+1 << ' ';
//        } cout << '\n';
        cur = 0;
        solve(0, n-1, 0);
        dat.clear();
        for(int j = 0; j < n; j++)
        {
//            cout << "J" << ": " << j << '\n';
            set<int> a, b, ca;
            for(auto v : ind[j])
            {
                for(auto kk : lc[v])
                {
                    a.insert(kk);
                    ca.insert(lead(kk));
                }
                for(auto kk : rc[v])
                {
                    if(ca.count(lead(kk)))
                        a.insert(kk);
                    else
                        b.insert(kk);
                }
            }
            if(!qrr(a, b))
                continue;
            int l = 0, r = ind[j].size()-1;
            while(l != r)
            {
                int m = (l+r) / 2;
                a.clear(); b.clear(); ca.clear();
                for(int v = l; v <= m; v++)
                {
                    for(auto k : lc[ind[j][v]])
                    {
                        a.insert(k);
                        ca.insert(lead(k));
                    }
                    for(auto k : rc[ind[j][v]])
                    {
                        if(ca.count(lead(k)))
                            a.insert(k);
                        else
                            b.insert(k);
                    }
                }
                if(qrr(a, b))
                    r = m;
                else
                    l = m+1;
            }
            vector<int> le, re;
            a.clear(); b.clear(); ca.clear();
            int kek = ind[j][l];
            for(auto v : lc[kek])
            {
                le.push_back(v); ca.insert(lead(v));
            }
            for(auto v : rc[kek])
            {
                if(ca.count(lead(v)))
                    le.push_back(v);
                else
                    re.push_back(v);
            }
            l = 0; r = le.size()-1;
            while(l != r)
            {
                int m = (l+r) / 2;
                a.clear(); b.clear(); ca.clear();
                for(int v = l; v <= m; v++)
                {
                    a.insert(le[v]);
                }
                for(auto v : re)
                {
                    b.insert(v);
                }
                if(qrr(a, b))
                    r = m;
                else
                    l = m+1;
            }
            int L = l;
            l = 0; r = re.size()-1;
            while(l != r)
            {
                int m = (l+r) / 2;
                a.clear(); b.clear(); ca.clear();
                for(int v = l; v <= m; v++)
                {
                    b.insert(re[v]);
                }
                for(auto v : le)
                {
                    a.insert(v);
                }
                if(qrr(a, b))
                    r = m;
                else
                    l = m+1;
            }
            int R = r;
            setRoad(le[L]+1, re[R]+1);
            comb(le[L], re[R]);
            break;
        }
    }
}
//
//int main()
//{
//    int n; cin >> n;
//    run(n);
//}






































/// shche ne vmerla Ykraina

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10