Submission #577293

#	Time	Username	Problem	Language	Result	Execution time	Memory
577293		zaneyu	Meetings (JOI19_meetings)	C++14	100 / 100	475 ms	1004 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld long double
#define pii pair<ll,int>
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=2e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
mt19937 rng(69);
namespace {
    bool in[maxn];
    
    int tmp[maxn];
    int a,b;
    vector<int> pv;
    void srt(int l,int r){
        if(l>=r) return;
        int mid=(l+r)/2;
        srt(l,mid),srt(mid+1,r);
        int p1=l,p2=mid+1;
        int p=0;
        while(p1<=mid and p2<=r){
            if(Query(a,pv[p1],pv[p2])==pv[p1]) tmp[p++]=pv[p1++];
            else tmp[p++]=pv[p2++];
        }
        while(p1<=mid) tmp[p++]=pv[p1++];
        while(p2<=r) tmp[p++]=pv[p2++];
        REP(i,r-l+1) pv[l+i]=tmp[i];
    }
    void rec(vector<int> v){
        if(sz(v)<=1) return;
        shuffle(ALL(v),rng);
        int p=(rng()%sz(v));
        map<int,vector<int>> cmpp;
        a=v[p],b=v[(p+1)%sz(v)];
        /*cout<<a<<'\n';
        for(int x:v) cout<<x<<' ';
        cout<<'\n';*/
        vector<int> vv;
        for(int x:v){
            if(x==a or x==b) continue;
            int asd=Query(a,b,x);
            if(asd==x){
                cmpp[x].pb(x);
                vv.pb(x);
            }
            else{
                cmpp[asd].pb(x);
            }
        }
        cmpp[a].pb(a),cmpp[b].pb(b);
        pv=vv;
        srt(0,sz(vv)-1);
        vv=pv;
        vv.emplace(vv.begin(),a);
        vv.pb(b);
        REP1(i,sz(vv)-1) Bridge(min(vv[i-1],vv[i]),max(vv[i-1],vv[i]));
        for(int x:vv){
            rec(cmpp[x]);
        }
    }
}

void Solve(int n) {
    vector<int> v;
    REP(i,n) v.pb(i);
    rec(v);
}

Compilation message (stderr)

meetings.cpp:35:10: warning: '{anonymous}::in' defined but not used [-Wunused-variable]
   35 |     bool in[maxn];
      |          ^~

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