Submission #983641

#	Time	Username	Problem	Language	Result	Execution time	Memory
983641		FZ_Melo	ICC (CEOI16_icc)	C++14	0 / 100	1 ms	604 KiB

icc

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

int n, tam1, tam2, c1, c2;
int arr1[101], arr2[101];
set<int> componentes;
vector<vector<int>> nums;

int buscaComp1(vector<int> &comp1, int t2){
    int l=0, r=comp1.size()-1;
    int aux[101];
    while(l<r){
        int mid=(l+r)/2;
        int pos=0;
        for(int i=l; i<=mid; i++){
            for(int x: nums[comp1[i]]){
                aux[pos++]=x;
            }
        }
        if(query(pos, t2, aux, arr2))
            r=mid;
        else
            l=mid+1;
    }
    int p1=0;
    for(int x: nums[comp1[l]]){
        arr1[p1++]=x;
    }
    tam1=nums[comp1[l]].size();
    return comp1[l];
}

int buscaComp2(vector<int> &comp2){
    int l=0, r=comp2.size()-1;
    int aux[101];
    while(l<r){
        int mid=(l+r)/2;
        int pos=0;
        for(int i=l; i<=mid; i++){
            for(int x: nums[comp2[i]]){
                aux[pos++]=x;
            }
        }
        if(query(tam1, pos, arr1, aux))
            r=mid;
        else
            l=mid+1;
    }
    int p2=0;
    for(int x: nums[comp2[l]]){
        arr2[p2++]=x;
    }
    tam2=nums[comp2[l]].size();
    return comp2[l];
}

void buscaComp(vector<int> &comp1, vector<int> &comp2){
    int p1=0, p2=0;
    if(c1!=0)
        return;
    for(int x: nums[comp1[0]])
        arr1[p1++]=x;
    for(int x: nums[comp2[0]])
        arr2[p2++]=x;
    if(query(p1, p2, arr1, arr2)){
        c1=buscaComp1(comp1, comp2.size());
        c2=buscaComp2(comp2);
        return;
    }
    vector<int> aux1, aux2, aux3, aux4;
    int t=comp1.size(), cnt=0;
    for(int x: comp1){
        if(cnt<t/2)
            aux1.push_back(x);
        else
            aux2.push_back(x);
        cnt++;
    }
    cnt=0;
    t=comp2.size();
    for(int x: comp2){
        if(cnt<t/2)
            aux3.push_back(x);
        else
            aux4.push_back(x);
        cnt++;
    }
    if(comp1.size()>1)
        buscaComp(aux1, aux2);
    if(comp2.size()>1)
        buscaComp(aux3, aux4);
}

int buscaNode1(){
    int l=0, r=nums[c1].size()-1;
    int aux[101];
    while(l<r){
        int mid=(l+r)/2;
        int pos=0;
        for(int i=l; i<=mid; i++){
            aux[pos++]=arr1[i];
        }
        if(query(pos, nums[c2].size(), aux, arr2))
            r=mid;
        else
            l=mid+1;
    }
    return arr1[l];
}

int buscaNode2(){
    int l=0, r=nums[c2].size()-1;
    int aux[101];
    while(l<r){
        int mid=(l+r)/2;
        int pos=0;
        for(int i=l; i<=mid; i++){
            aux[pos++]=arr2[i];
        }
        if(query(nums[c1].size(), pos, arr1, aux))
            r=mid;
        else
            l=mid+1;
    }
    return arr2[l];
}


pair<int, int> buscaNode(){
    int p1=0, p2=0;
    for(int x: nums[c1]){
        arr1[p1++]=x;
    }
    for(int x: nums[c2]){
        arr2[p2++]=x;
    }
    int a, b;
    a=buscaNode1();
    b=buscaNode2();
    if(nums[c1].size()>=nums[c2].size()){
        componentes.erase(c2);
        for(int x: nums[c2]){
            nums[c1].push_back(x);
        }
    }
    else{
        componentes.erase(c1);
        for(int x: nums[c1]){
            nums[c2].push_back(x);
        }
    }
    return {a, b};
}

void run(int N){
    n=N;
    nums.clear();
    componentes.clear();
    nums.resize(n+1);
    for(int i=1; i<=n; i++){
        componentes.insert(i);
        nums[i].push_back(i);
    }
    for(int k=0; k<n-1; k++){
        int cnt=0;
        int t=componentes.size();
        vector<int> comp1, comp2;
        for(int x: componentes){
            if(cnt<t/2)
                comp1.push_back(x);
            else
                comp2.push_back(x);
        }
        c1=0;
        c2=0;
        buscaComp(comp1, comp2);
        pair<int, int> node=buscaNode();
        setRoad(node.first, node.second);
    }
}

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