Submission #1005672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005672		alexdd	ICC (CEOI16_icc)	C++17	100 / 100	99 ms	852 KiB

icc

#include "icc.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> comp[105];
vector<int> con[105];
int cntc;
bool visited[105];
void dfs(int nod, int c)
{
    visited[nod]=1;
    comp[c].push_back(nod);
    for(auto adj:con[nod])
        if(!visited[adj])
            dfs(adj,c);
}
int a[105],b[105],cnta,cntb;
int gaseste(int v[], int cntv, int u[], int cntu)
{
    int st,dr,ans;
    st=0;
    dr=cntv-2;
    ans=cntv-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(query(mij+1,cntu,v,u))
        {
            ans=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    return v[ans];
}
void run(int N)
{
    for(int pas=1;pas<N;pas++)
    {
        for(int i=1;i<=N;i++) visited[i]=0;
        cntc=0;
        for(int i=1;i<=N;i++)
        {
            if(!visited[i])
            {
                comp[cntc].clear();
                dfs(i,cntc);
                cntc++;
            }
        }
        bool gasit=0;
        for(int i=0;(1<<i)<cntc;i++)
        {
            cnta=cntb=0;
            for(int j=0;j<cntc;j++)
            {
                if(((1<<i)&j))
                {
                    for(auto x:comp[j]) a[cnta++]=x;
                }
                else
                {
                    for(auto x:comp[j]) b[cntb++]=x;
                }
            }
            if(query(cnta,cntb,a,b))
            {
                gasit=1;
                break;
            }
        }
        assert(gasit);
        random_shuffle(a,a+cnta);
        random_shuffle(b,b+cntb);
        int x = gaseste(a,cnta,b,cntb);
        int y = gaseste(b,cntb,a,cnta);
        setRoad(x,y);
        con[x].push_back(y);
        con[y].push_back(x);
    }
}

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