Submission #1061841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061841		oscar1f	Meetings (JOI19_meetings)	C++17	100 / 100	366 ms	1564 KiB

meetings

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

void afficher(vector<int> v) {
    for (int i:v) {
        cout<<i<<" ";
    }
    cout<<endl;
}

void construire(int a,int b) {
    Bridge(min(a,b),max(a,b));
}

void calc(vector<int> v) {
    int nbSom=v.size();
    //afficher(v);
    if (nbSom<2) {
        return;
    }
    if (nbSom==2) {
        construire(v[0],v[1]);
        return;
    }
    int rand1=rand()%nbSom,rand2=rand()%(nbSom-1);
    int somDeb=v[rand1],somFin=v[(rand1+rand2+1)%nbSom];
    unordered_map<int,int> dv,corres;
    dv[somDeb]=1;
    dv[somFin]=1;
    corres[somDeb]=1;
    corres[somFin]=2;
    int tailleChaine=2,ans;
    vector<vector<int>> suiv;
    suiv={{},{somDeb},{somFin}};
    //cout<<"?"<<somDeb<<" "<<somFin<<endl;
    for (int i:v) {
        if (dv[i]==0) {
            dv[i]=1;
            ans=Query(i,somDeb,somFin);
            if (ans==i) {
                tailleChaine++;
                suiv.push_back({i});
                corres[i]=tailleChaine;
            }
            else if (dv[ans]==0) {
                dv[ans]=1;
                tailleChaine++;
                suiv.push_back({ans,i});
                corres[ans]=tailleChaine;
            }
            else {
                suiv[corres[ans]].push_back(i);
            }
        }
    }
    for (auto w:suiv) {
        //cout<<"!";
        //afficher(w);
        calc(w);
    } 
    int nouv,deb,fin,mid;
    vector<int> ordre={somDeb,somFin},nouvOrdre;
    for (int i=3;i<=tailleChaine;i++) {
        nouv=suiv[i][0];
        deb=0;
        fin=i-3;
        while (deb!=fin) {
            mid=(deb+fin)/2;
            ans=Query(ordre[mid],ordre[mid+1],nouv);
            if (ans==nouv) {
                deb=mid;
                fin=mid;
            }
            else if (ans==ordre[mid]) {
                fin=mid-1;
            }
            else {
                deb=mid+1;
            }
        }
        nouvOrdre.clear();
        for (int j=0;j<i-1;j++) {
            nouvOrdre.push_back(ordre[j]);
            if (j==deb) {
                nouvOrdre.push_back(nouv);
            }
        }
        ordre=nouvOrdre;
    }
    //cout<<"#";
    //afficher(ordre);
    for (int i=0;i<tailleChaine-1;i++) {
        construire(ordre[i],ordre[i+1]);
    }
}

void Solve(int N) {
    srand(time(NULL));
    //int x = Query(0, 1, 2);
    vector<int> v;
    for (int i=0;i<N;i++) {
        v.push_back(i);
    }
    calc(v);
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71