Submission #706738

#	Time	Username	Problem	Language	Result	Execution time	Memory
706738		Antekb	Meetings (JOI19_meetings)	C++14	100 / 100	755 ms	1216 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")
 
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define pp(x) pop_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
 
using namespace std;
 
///~~~~~~~~~~~~~~~~~~~~~~~~~~
 
template <typename H, typename T> 
ostream& operator<<(ostream& os, pair<H, T> m){
	return os <<"("<< m.st<<", "<<m.nd<<")";
}
template <typename H> 
ostream& operator<<(ostream& os, vector<H> V){
	os<<"{";
	for(int i=0; i<V.size(); i++){
		if(i)os<<" ";
		os<<V[i];
	}
	os<<"}";
	return os;
}
 
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
//#define deb(x...) ;
 
///~~~~~~~~~~~~~~~~~~~~~~~~~
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

 
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int P;
void bridge(int a, int b){
	if(a>b)swap(a, b);
	Bridge(a, b);
}
void solve(vi V){
	deb(V);
	int n=V.size();
	if(n==2)bridge(V[0], V[1]);
	if(n<=2)return;
	swap(V[0], V[rng()%n]);
	swap(V[n-1], V[1+(rng()%(n-1))]);
	int pp=V[0], kk=V[n-1];
	deb(pp, kk);
	vii V2(n);
	for(int i=0; i<n; i++){
		if(i==0 || i+1==n)V2[i]=mp(V[i], V[i]);
		else V2[i]=mp(Query(V[0], V[i], V[n-1]), V[i]);
	}
	V.clear();
	sor(V2);
	vi V3;
	deb("a");
	for(int i=0; i<=n; i++){
		if(i==n || (i && V2[i].st!=V2[i-1].st)){
			deb(V3);
			solve(V3);
			if(V2[i-1].st!=pp && V2[i-1].st!=kk)V.pb(V2[i-1].st);
			V3.clear();
		}
		if(i!=n)V3.pb(V2[i].nd);
	}
	P=pp;
	sort(V.begin(), V.end(), [](int a, int b){if(Query(P, a, b)==a)return 1;else return 0;});
	for(int i=1; i<V.size(); i++){
		bridge(V[i], V[i-1]);
	}
	if(V.size()){
		bridge(pp, V[0]);
		bridge(V.back(), kk);
	}
	else bridge(pp, kk);
}
void Solve(int N) {
	vi V(N);
	iota(all(V), 0);
	solve(V);
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(vi)':
meetings.cpp:101:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for(int i=1; i<V.size(); i++){
      |               ~^~~~~~~~~
meetings.cpp: In instantiation of 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>) [with H = int; std::ostream = std::basic_ostream<char>]':
meetings.cpp:40:30:   required from 'void debug(H, T ...) [with H = std::vector<int>; T = {}]'
meetings.cpp:73:2:   required from here
meetings.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~

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