oj.uz

Submission #983629

# Submission time Handle Problem Language Result Execution time Memory
983629 2024-05-15T19:32:24 Z FZ_Melo ICC (CEOI16_icc) C++14
0 / 100
 1 ms 348 KB 
#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!=-1)
        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);
        }
        buscaComp(comp1, comp2);
        pair<int, int> node=buscaNode();
        setRoad(node.first, node.second);
    }
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 29.0

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

Subtask #6
0 / 10.0

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