Submission #125108

#	Time	Username	Problem	Language	Result	Execution time	Memory
125108		johutha	ICC (CEOI16_icc)	C++14	90 / 100	168 ms	632 KiB

icc

#include <vector>
#include <iostream>
#include "icc.h"
#include <set>
#include <algorithm>

using namespace std;

int log2(int n)
{
    return 32 - __builtin_clz(n) - 1;
}

int _query(int sa, int sb, int a[], int b[])
{
    vector<int> na;
    vector<int> nb;

    for (int i = 0; i < sa; i++)
    {
        na.push_back(a[i] + 1);
    }
    for (int i = 0; i < sb; i++)
    {
        nb.push_back(b[i] + 1);
    }
    return query(sa, sb, na.data(), nb.data());
}

struct unionfind
{
    vector<int> chef;

    int find(int x)
    {
        if(chef[x] == x) return x;
        return chef[x] = find(chef[x]);
    }

    void unite(int a, int b)
    {
        if (rand() & 1) chef[find(a)] = find(b);
        else chef[find(b)] = find(a);
    }

    void init(int n)
    {
        chef.resize(n);
        for(int i = 0; i < n; i++) chef[i] = i;
    }
};

int binsearch(vector<int> &tosearch, vector<int> &other)
{
    int n = tosearch.size();

    int l2 = log2(n) + 1;

    int p = 0;

    for (int i = 0; i < l2; i++)
    {
        vector<int> search;
        for (int j = 0; j < n; j++)
        {
            if ((1<<i) & j) search.push_back(tosearch[j]);
        }
        p += (1<<i)*_query(search.size(), other.size(), search.data(), other.data());
    }
    return tosearch[p];
}

void run(int n)
{
    unionfind uf;
    uf.init(n);
    srand(852935);

    for (int z = 0; z < n - 1; z++)
    {
        set<int> c;
        for (int i = 0; i < n; i++)
        {
            c.insert(uf.find(i));
        }
        vector<int> components;
        for (int i : c)
        {
            components.push_back(i);
        }
        int cs = components.size();

        vector<int> compind(n);
        for (int i = 0; i < cs; i++)
        {
            compind[components[i]] = i;
        }
        int l2 = log2(cs) + 1;
        vector<int> a;
        vector<int> b;

        for (int cl = 0; cl < l2; cl++)
        {
            a.clear();
            b.clear();
            for (int i = 0; i < n; i++)
            {
                if ((1<<cl) & compind[uf.find(i)]) a.push_back(i);
                else b.push_back(i);
            }
            if (_query(a.size(), b.size(), a.data(), b.data())) break;
        }
        int first = binsearch(a, b);
        int second = binsearch(b, a);
        setRoad(first + 1, second + 1);
        uf.unite(first, second);
    }
}

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