제출 #1144085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144085		MongHwa	ICC (CEOI16_icc)	C++20	0 / 100	23 ms	624 KiB

icc

#include "icc.h"
#include <vector>
#include <set>
using namespace std;

int parent[105];
set<int> comp[105];
int num[105];

int find(int x)
{
    if(parent[x] < 0)
        return x;
    parent[x] = find(parent[x]);
    return parent[x];
}

void comb(int a, int b)
{
    a = num[a];
    b = num[b];

    if(a == b)
        return;
    if(a > b)
        swap(a, b);
    
    for(int x : comp[b])
    {
        comp[a].insert(x);
        num[x] = a;
    }

    comp[b].clear();
}

void run(int n) {
    for(int i = 1; i <= n; i++)
    {
        comp[i-1].insert(i);
        num[i] = i-1;
    }

    for(int z = 0; z < n-1; z++)
    {
        for(int i = 0; (1<<i) < n-z; i++)
        {
            int asize = 0, bsize = 0;
            for(int j = 0; j < n-z; j++)
            {
                if(j & (1<<i))
                    asize += comp[j].size();
                else
                    bsize += comp[j].size();
            }

            int arr[asize], brr[bsize];
            int pos1 = 0, pos2 = 0;
            for(int j = 0; j < n-z; j++)
            {
                if(j & (1<<i))
                    for(int x : comp[j])
                        arr[pos1++] = x;
                else
                    for(int x : comp[j])
                        brr[pos2++] = x;
            }

            if(query(asize, bsize, arr, brr))
            {
                int a, b;
                vector<int> v;
                for(int j = 0; j < asize; j++)
                    v.push_back(arr[j]);

                while(1)
                {   
                    if(asize == 1)
                    {
                        a = v[0];
                        break;
                    }

                    int trr[asize/2];
                    for(int j = 0; j < asize/2; j++)
                        trr[j] = v[j];
                    
                    if(query(asize/2, bsize, trr, brr))
                    {
                        v.erase(v.begin()+asize/2+1, v.end());
                        asize /= 2;
                        if(asize == 1)
                        {
                            a = v[0];
                            break;
                        }
                    }
                    else
                    {
                        v.erase(v.begin(), v.begin()+asize/2);
                        asize = asize/2 + asize%2;
                        if(asize == 1)
                        {
                            a = v[0];
                            break;
                        }
                    }
                }

                v.clear();
                for(int j = 0; j < bsize; j++)
                    v.push_back(brr[j]);

                int arr2[1] = {a};
                while(1)
                {   
                    if(bsize == 1)
                    {
                        b = v[0];
                        break;
                    }

                    int trr[bsize/2];
                    for(int j = 0; j < bsize/2; j++)
                        trr[j] = v[j];
                    
                    if(query(1, bsize/2, arr2, trr))
                    {
                        v.erase(v.begin()+bsize/2+1, v.end());
                        bsize /= 2;
                        if(bsize == 1)
                        {
                            b = v[0];
                            break;
                        }
                    }
                    else
                    {
                        v.erase(v.begin(), v.begin()+bsize/2);
                        bsize = bsize/2 + bsize%2;
                        if(bsize == 1)
                        {
                            b = v[0];
                            break;
                        }
                    }
                }

                setRoad(a, b);
                comb(a, b);

                int mx = max(num[a], num[b]);
                for(int j = mx; j+1 < n-z; j++)
                {
                    for(int x : comp[j+1])
                        num[x] = j;
                    comp[j] = comp[j+1];
                }
                break;
            }
        }
    }
}

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