Submission #362433

#	Time	Username	Problem	Language	Result	Execution time	Memory
362433		alextodoran	ICC (CEOI16_icc)	C++17	100 / 100	153 ms	748 KiB

icc

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

typedef long long ll;

const int N_MAX = 102;

const int BITS = 7;

int query (int sa, int sb, int a[], int b[]);

void setRoad (int a, int b);

vector <int> edges[N_MAX];

vector <int> component[N_MAX];
int cntComponents;

bool visited[N_MAX];

void dfs (int u)
{
    visited[u] = true;
    component[cntComponents].push_back(u);
    for(int v : edges[u])
        if(visited[v] == false)
            dfs(v);
}

int a[N_MAX], b[N_MAX];

int ca[N_MAX], cb[N_MAX];

void run (int n)
{
    for(int t = 1; t < n; t++)
    {
        int U, V;
        for(int i = 1; i <= n; i++)
            visited[i] = false;
        for(int i = 1; i <= n; i++)
            if(visited[i] == false)
            {
                cntComponents++;
                dfs(i);
            }
        int cnta, cntb;
        for(int bit = 0; bit < BITS; bit++)
        {
            cnta = 0;
            cntb = 0;
            for(int i = 1; i <= cntComponents; i++)
                if((i >> bit) & 1)
                {
                    for(int u : component[i])
                        a[cnta++] = u;
                }
                else
                {
                    for(int u : component[i])
                        b[cntb++] = u;
                }
            if(query(cnta, cntb, a, b) == true)
                break;
        }
        int l, r;
        l = 0;
        r = cnta - 1;
        while(l < r)
        {
            int mid = ((l + r) >> 1);
            if(query(mid - l + 1, cntb, a + l, b) == true)
                r = mid;
            else
                l = mid + 1;
        }
        U = a[l];
        l = 0;
        r = cntb - 1;
        while(l < r)
        {
            int mid = ((l + r) >> 1);
            if(query(cnta, mid - l + 1, a, b + l) == true)
                r = mid;
            else
                l = mid + 1;
        }
        V = b[l];
        setRoad(U, V);
        edges[U].push_back(V);
        edges[V].push_back(U);
        for(int i = 1; i <= cntComponents; i++)
            component[i].clear();
        cntComponents = 0;
    }
}

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