Submission #1171092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171092		mbk	Meetings (JOI19_meetings)	C++20	100 / 100	636 ms	1768 KiB

meetings

#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;
auto seed= chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937_64 rng(seed);
constexpr int MN=2e3+10;
bool com(int a,int b){return a<b;}
void droga(int a,int b,vector<int> wie)
{
//    cout<<"droga "<<a<<" "<<b<<"\n";
    //for(auto x: wie) cout<<x<<" ";
//    cout<<"\n";
    shuffle(wie.begin(),wie.end(),rng);
    if (wie.size()==0)
    {
//        cout<<"tu0\n";
        Bridge(min(a,b),max(a,b)); 
        return ;
    } 
    int c=wie[0];
    if(wie.size()==1)
    {
//      cout<<"tu1\n";
        Bridge(min(a,c),max(a,c));
        Bridge(min(b,c),max(b,c));
        return ;
    }
    vector<int> ve1,ve2;

    for(auto x: wie)
    {
        if(x==c) continue;
        int sr=Query(a,c,x);
        if (sr==c) ve2.push_back(x);
        else ve1.push_back(x);
    }
    droga(a,c,ve1);
    droga(b,c,ve2);
}
void rozw(vector<int> wie)
{
    if(wie.size()<2) return ;

    if (wie.size()==2)
    {
        sort(wie.begin(),wie.end(),com);
        Bridge(wie[0],wie[1]);
        return ;
    }
    int a=wie[0];
    int b=wie[1];
    map<int,vector<int>> mp;
    set<int> st;
    for(auto x: wie)
    {
        if(x==a || x==b) continue;
        int sr=0;
        if (mp[x].size()!=0) sr=x;
        else sr=Query(a,b,x);
        st.insert(sr);
        mp[sr].push_back(x);
    }
    mp[a].push_back(a);
    mp[b].push_back(b);
    st.erase(a);
    st.erase(b);
    vector<int> he;
    for(auto x: st) he.push_back(x);
    droga(a,b,he);
    for(auto ve: mp) rozw(ve.second);
}
void Solve(int n)
{
    vector<int> wie;
    for(int i=0; i<n; i++) wie.push_back(i);
    shuffle(wie.begin(),wie.end(),rng);
    rozw(wie);
}

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