제출 #1289928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289928		lucasdmy	ICC (CEOI16_icc)	C++20	0 / 100	15 ms	612 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>component[110], comp(110);
int edges=0, ata, atb, n;
/*int query(int sa, int sb, int a[], int b[]){
    cout<<"Query!"<<endl;
    for(int k=0;k<sa;k++){
        cout<<a[k]<<' ';
    }
    cout<<endl;
    for(int k=0;k<sb;k++){
        cout<<b[k]<<' ';
    }
    cout<<endl;
    int v;
    cin>>v;
    return v;
}*/
int find_edge(vector<int>a, vector<int>b){
    int p1=0, p2=a.size();
    cout<<"binary search!"<<endl;
    while(p1!=p2){
        int middle=(p1+p2)/2;
        int auxa[middle-p1+1];
        for(int k=p1;k<=middle;k++){
            auxa[k-p1]=a[k];
        }
        int auxb[b.size()];
        for(int k=0;k<b.size();k++){
            auxb[k]=b[k];
        }
        int aux1=query(middle-p1+1, b.size(), auxa, auxb);
        if(aux1){
            p2=middle;
        }else{
            p1=middle+1;
        }
    }
    return a[p2];
}
/*void setRoad(int a, int b){
    cout<<"ans "<<a<<' '<<b<<endl;
    if(a!=ata or b!=atb){
        if(b!=ata or a!=atb){
            cout<<"wrong road"<<endl;
            exit(0);
        }
    }
}*/
void merge(int c1, int c2){
    for(int k=0;k<component[c2].size();k++){
        component[c1].push_back(component[c2][k]);
        comp[component[c2][k]]=c1;
    }
    component[c2].clear();
    for(int k=1;k<=n;k++){
        if(component[k].size()==0){
            for(int i=0;i<component[k+1].size();i++){
                component[k].push_back(component[k+1][i]);
                comp[component[k+1][i]]=k;
            }
            component[k+1].clear();
        }
    }
}
void run(int n){
    while(edges!=n-1){
        cin>>ata>>atb;
        edges++;
        if(edges==1){
            for(int k=1;k<=n;k++){
                component[k].push_back(k);
                comp[k]=k;
            }
        }
        vector<int>group1, group2;
        for(int k=n-edges+1;k>=1;k--){
            group2.insert(group2.end(), component[k].begin(), component[k].end());
        }
        for(int k=1;k<=n-edges+1;k++){
            for(int i=0;i<component[k].size();i++){
                group2.pop_back();
            }
            group1.insert(group1.end(), component[k].begin(), component[k].end());
            int auxa[group1.size()], auxb[group2.size()];
            for(int k=0;k<group1.size();k++){
                auxa[k]=group1[k];
            }
            for(int k=0;k<group2.size();k++){
                auxb[k]=group2[k];
            }
            if(query(group1.size(), group2.size(), auxa, auxb)){
                break;
            }
        }
        int n1, n2;
        n1=find_edge(group1, group2);
        swap(group1, group2);
        n2=find_edge(group1, group2);
        setRoad(n1, n2);
        merge(comp[n1], comp[n2]);
        for(int k=1;k<=n;k++){
            for(int i=0;i<component[k].size();i++){
                cout<<component[k][i]<<' ';
            }
            cout<<endl;
        }
        for(int k=1;k<=n;k++){
            cout<<comp[k]<<' ';
        }
        cout<<endl;
    }
}/*
int main(){
    cin>>n;
    run(n);
}*/

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