Submission #443914

#	Time	Username	Problem	Language	Result	Execution time	Memory
443914		prvocislo	ICC (CEOI16_icc)	C++17	100 / 100	148 ms	960 KiB

icc

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

const int maxn = 105;
int find_vr(int na, int nb, int a[], int b[])
{
    int lo = 1, hi = na; 
    while (lo < hi)
    {
        int mi = (lo + hi) >> 1;
        int *c = new int[maxn];
        for (int i = 0; i < mi; i++) c[i] = a[i];
        if (query(mi, nb, c, b)) hi = mi;
        else lo = mi+1;
    }
    return a[lo-1]-1;
}
vector<int> c[maxn], g[maxn];
int vis[maxn], a[maxn], b[maxn];
void dfs(int u, int col)
{
    vis[u] = 1, c[col].push_back(u);
    for (int v : g[u]) if (!vis[v]) dfs(v, col);
}
void run(int n)
{
    for (int e = 0; e < n-1; e++)
    {
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) c[i].clear();
        int cnt = 0;
        for (int i = 0; i < n; i++) if (!vis[i]) dfs(i, cnt++);
        for (int i = 0; (1 << i) < cnt; i++)
        {
            int na = 0, nb = 0;
            for (int j = 0; j < cnt; j++) 
            {
                if ((1 << i) & j) for (int vr : c[j]) a[na++] = vr+1;
                else for (int vr : c[j]) b[nb++] = vr+1;
            }
            if (query(na, nb, a, b))
            {
                int u = find_vr(na, nb, a, b);
                int v = find_vr(nb, na, b, a);
                g[u].push_back(v), g[v].push_back(u);
                setRoad(u+1, v+1);
                break;
            }
        }
    }
}

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