Submission #112562

#	Time	Username	Problem	Language	Result	Execution time	Memory
112562		reality	Meetings (JOI19_meetings)	C++17	100 / 100	1127 ms	948 KiB

meetings

#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int n;
void shit(int x,int y) {
	if (x > y)
		Bridge(y,x);
	else
		Bridge(x,y);
}
#define Bridge shit
void Go(vi p) {
	if (p.size() <= 1) 
		return;
	else 
	if (p.size() == 2) {
		Bridge(p[0],p[1]);
	}
	else {
		const int sz = p.size();
		random_shuffle(all(p));
		vector < pii > v;
		for (int i = 2;i < sz;++i) {
			v.pb(mp(Query(p[0],p[1],p[i]),p[i]));
		}
		sort(all(v));
		vi w;
		w.pb(p[0]);
		w.pb(p[1]);
		for (int i = 0;i < v.size();) {
			int j = i;
			vi vr;
			w.pb(v[i].fi);
			while (j < v.size() && v[i].fi == v[j].fi)
				vr.pb(v[j].se),++j;
			vr.pb(v[i].fi);
			sort(all(vr));
			vr.resize(unique(all(vr)) - vr.begin());
			Go(vr);
			i = j;
		}
		sort(all(w));
		w.resize(unique(all(w)) - w.begin());
		sort(all(w),[&](int x,int y) {
				if (x == p[0] || y == p[1])
					return true;
				if (y == p[0] || x == p[1])
					return false;
				return x == Query(p[0],x,y);
			});
		for (int i = 0;i + 1 < w.size();++i)
			Bridge(w[i],w[i + 1]);
	}
}
void Solve(int NN) {
	srand(time(0));
	n = NN;
	vi p;
	for (int i = 0;i < n;++i)
		p.pb(i);
	Go(p);
}

Compilation message (stderr)

meetings.cpp: In function 'void Go(std::vector<int>)':
meetings.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0;i < v.size();) {
                  ~~^~~~~~~~~~
meetings.cpp:50:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (j < v.size() && v[i].fi == v[j].fi)
           ~~^~~~~~~~~~
meetings.cpp:67:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0;i + 1 < w.size();++i)
                  ~~~~~~^~~~~~~~~~

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