제출 #1084551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1084551		MMihalev	ICC (CEOI16_icc)	C++14	100 / 100	105 ms	856 KiB

icc

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<tuple>
#include<set>
#include<map>
#include<random>
#include<chrono>
#include<unordered_map>
#include "icc.h"
using namespace std;
const int MAX_N=1e3+3;
int a[MAX_N];
int b[MAX_N];
int sza,szb;
vector<int>v1,v2;
vector<vector<int>>comps;
vector<int>comp;
vector<int>g[MAX_N];
int used[MAX_N];

void dfs(int u)
{
    used[u]=1;
    comp.push_back(u);
    for(int v:g[u])
    {
        if(used[v])continue;
        dfs(v);
    }
}
void toarray(int l,int r,vector<int>& v,bool f)
{
    if(f==0)
    {
        sza=0;
        for(int i=l;i<=r;i++)
        {
            a[sza++]=v[i];
        }
    }
    else
    {
        szb=0;
        for(int i=l;i<=r;i++)
        {
            b[szb++]=v[i];
        }
    }
}
pair<int,int>guessedge()
{
    int l=0,r=v1.size()-1,u,v;
    while(l!=r)
    {
        int mid=(l+r)/2;
        toarray(l,mid,v1,0);
        toarray(0,v2.size()-1,v2,1);
        if(query(sza,szb,a,b))
        {
            r=mid;
        }
        else l=mid+1;
    }
    u=v1[l];
    int posu=l;

    l=0;
    r=v2.size()-1;
    while(l!=r)
    {
        int mid=(l+r)/2;
        toarray(posu,posu,v1,0);
        toarray(l,mid,v2,1);
        if(query(sza,szb,a,b))
        {
            r=mid;
        }
        else l=mid+1;
    }
    v=v2[l];
    return {u,v};
}
vector<vector<int>>c1,c2;
void toarray2()
{
    sza=0;
    for(auto c:c1)
    {
        for(auto d:c)
        {
            a[sza++]=d;
        }
    }
    szb=0;
    for(auto c:c2)
    {
        for(auto d:c)
        {
            b[szb++]=d;
        }
    }
}
bool in(int bit,int mask)
{
    return (((1<<bit)&(mask))!=0);
}
void separate()
{
    int id1=0,id2=0,xo=0,bit=0;
    int sz=comps.size()-1;
    for(int bi=0;(1<<bi)<=sz;bi++)
    {
        c1.clear();c2.clear();
        for(int i=0;i<=sz;i++)
        {
            if(in(bi,i))
            {
                c1.push_back(comps[i]);
            }
            else c2.push_back(comps[i]);
        }

        toarray2();
        if(query(sza,szb,a,b)){xo+=(1<<bi);bit=bi;}
    }
    id2+=(1<<bit);

    for(int bi=0;(1<<bi)<=sz;bi++)
    {
        if(bi==bit)continue;

        if(in(bi,xo))
        {
            c1.clear();c2.clear();
            for(int i=0;i<=sz;i++)
            {
                if(in(bi,i)==0 && in(bit,i)==0)c1.push_back(comps[i]);
            }
            for(int i=0;i<=sz;i++)
            {
                if(in(bi,i)==1 && in(bit,i)==1)c2.push_back(comps[i]);
            }

            toarray2();
            if(query(sza,szb,a,b))
            {
                id2+=(1<<bi);
            }
            else id1+=(1<<bi);
        }
        else
        {
            c1.clear();c2.clear();
            for(int i=0;i<=sz;i++)
            {
                if(in(bi,i)==0 && in(bit,i)==0)c1.push_back(comps[i]);
            }
            for(int i=0;i<=sz;i++)
            {
                if(in(bi,i)==0 && in(bit,i)==1)c2.push_back(comps[i]);
            }

            toarray2();
            if(!query(sza,szb,a,b))
            {
                id2+=(1<<bi);
                id1+=(1<<bi);
            }
        }
    }

    v1=comps[id1];
    v2=comps[id2];
}
void run(int N)
{
    for(int steps=1;steps<=N-1;steps++)
    {
        comps.clear();
        for(int i=1;i<=N;i++)
        {
            used[i]=0;
        }
        for(int i=1;i<=N;i++)
        {
            if(used[i]==0)
            {
                comp.clear();
                dfs(i);
                comps.push_back(comp);
            }
        }

        separate();

        int u,v;
        tie(u,v)=guessedge();
        setRoad(u,v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
}

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