oj.uz

Submission #983581

# Submission time Handle Problem Language Result Execution time Memory
983581 2024-05-15T18:35:39 Z FZ_Melo ICC (CEOI16_icc) C++14
0 / 100
 4 ms 856 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

int n, tam1, tam2;
vector<int> comp1;
vector<int> comp2;
vector<int> comp3;
int arr1[101], arr2[101];
set<int> componentes;
vector<vector<int>> nums;

int buscaComp1(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(){
    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];
}

pair<int, int> buscaComp(){
    int p1=0, p2=0;
    int t=componentes.size(), cnt=0;
    int a, b;
    comp1.clear();
    comp2.clear();
    comp3.clear();
    for(int it: componentes){
        if(cnt<t/2){
            for(int x: nums[it])
                arr1[p1++]=x;
            comp1.push_back(it);
        }
        else{
            for(int x: nums[it])
                arr2[p2++]=x;
            comp2.push_back(it);
        }
        cnt++;
    }
    if(query(p1, p2, arr1, arr2)){
        a=buscaComp1(p2);
        b=buscaComp2();
    }
    else{
        p1=p2=0;
        cnt=0;
        comp3=comp1;
        t=comp3.size();
        comp1.clear();
        comp2.clear();
        for(int c: comp3){
            if(cnt<t/2){
                for(int x: nums[c]){
                    arr1[p1++]=x;
                }
                comp1.push_back(c);
            }
            else{
                for(int x: nums[c]){
                    arr2[p2++]=x;
                }
                comp2.push_back(c);
            }
            cnt++;
        }
        if(query(p1, p2, arr1, arr2)){
            a=buscaComp1(p2);
            b=buscaComp2();
        }
        else{
            p1=p2=0;
            cnt=0;
            comp1.clear();
            comp2.clear();
            comp3.clear();
            t=componentes.size();
            for(int c: componentes){
                if(cnt>=t/2){
                    comp3.push_back(c);
                }
                cnt++;
            }
            t=comp3.size();
            cnt=0;
            p1=p2=0;
            for(int c: comp3){
                if(cnt<t/2){
                    for(int x: nums[c])
                        arr1[p1++]=x;
                    comp1.push_back(c);
                }
                else{
                    for(int x: nums[c])
                        arr2[p2++]=x;
                    comp2.push_back(c);
                }
                cnt++;
            }
            a=buscaComp1(p2);
            b=buscaComp2();
        }
    }
    return {a, b};
}

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


pair<int, int> buscaNode(int c1, int c2){
    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(c1, c2);
    b=buscaNode2(a, c2);
    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();
    comp1.clear();
    comp2.clear();
    comp3.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++){
        pair<int, int> comp=buscaComp();
        pair<int, int> node=buscaNode(comp.first, comp.second);
        setRoad(node.first, node.second);
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Ok! 111 queries used.
2 Incorrect 1 ms 600 KB Wrong road!
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 856 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Wrong road!
2 Halted 0 ms 0 KB -