Submission #211739

#	Time	Username	Problem	Language	Result	Execution time	Memory
211739		zscoder	Hamburg Steak (JOI20_hamburg)	C++17	21 / 100	3073 ms	12996 KiB

hamburg

#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;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int grp[222222];

vector<int> Xcoord,Ycoord;
int n,k; 
vector<ii> ans;
vector<pair<ii,ii> > vec;

void getpt(int gp)
{
	int minX = -1;
	int maxX = int(1e9)+1;
	int minY = -1;
	int maxY = int(1e9)+1;
	for(int i=0;i<n;i++)
	{
		if(grp[i]==gp)
		{
			maxX=min(maxX,vec[i].fi.se);
			minX=max(minX,vec[i].fi.fi);
			maxY=min(maxY,vec[i].se.se);
			minY=max(minY,vec[i].se.fi);
		}
	}
	if(maxX<minX||minX<0) maxX=minX=0;
	if(maxY<minY||minY<0) maxY=minY=0;
	//cerr<<gp<<' '<<minX<<' '<<maxX<<' '<<minY<<' '<<maxY<<'\n';
	ans.pb({Xcoord[minX],Ycoord[minY]});
}

vi adj[2222];

bool intersect(int i, int j)
{
	return (vec[i].fi.se>=vec[j].fi.fi&&vec[j].fi.se>=vec[i].fi.fi&&vec[i].se.se>=vec[j].se.fi&&vec[j].se.se>=vec[i].se.fi);
}

bool visited[2222];

void dfs(int u, int bit=1, int p=-1)
{
	visited[u]=1;
	for(int v:adj[u])
	{
		if(v==p) continue;
		if(bit==2&&((grp[u]&1)!=(grp[v]&1))) continue;
		if(!visited[v])
		{
			grp[v]=grp[u]^bit;
			dfs(v,bit,u);
		}
	}
}

pair<ii,ii> B[4];
pair<ii,ii> def = {{-1,int(1e9)},{-1,int(1e9)}};

pair<ii,ii> inter(pair<ii,ii> a, pair<ii,ii> b)
{
	pair<ii,ii> c;
	c.fi.fi = max(a.fi.fi,b.fi.fi);
	c.fi.se = min(a.fi.se,b.fi.se);
	c.se.fi = max(a.se.fi,b.se.fi);
	c.se.se = min(a.se.se,b.se.se);
	return c;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		Xcoord.pb(x1); Xcoord.pb(x2);
		Ycoord.pb(y1); Ycoord.pb(y2);
		vec.pb({{x1,x2},{y1,y2}});
	}
	sort(vec.begin(),vec.end());
	sort(Xcoord.begin(),Xcoord.end()); Xcoord.erase(unique(Xcoord.begin(),Xcoord.end()),Xcoord.end());
	sort(Ycoord.begin(),Ycoord.end()); Ycoord.erase(unique(Ycoord.begin(),Ycoord.end()),Ycoord.end());
	for(int i=0;i<vec.size();i++)
	{
		vec[i].fi.fi=lower_bound(Xcoord.begin(),Xcoord.end(),vec[i].fi.fi)-Xcoord.begin();
		vec[i].fi.se=lower_bound(Xcoord.begin(),Xcoord.end(),vec[i].fi.se)-Xcoord.begin();
		vec[i].se.fi=lower_bound(Ycoord.begin(),Ycoord.end(),vec[i].se.fi)-Ycoord.begin();
		vec[i].se.se=lower_bound(Ycoord.begin(),Ycoord.end(),vec[i].se.se)-Ycoord.begin();
		//cerr<<vec[i].fi.fi<<' '<<vec[i].fi.se<<' '<<vec[i].se.fi<<' '<<vec[i].se.se<<'\n';
	}
	vi p(n);
	for(int i=0;i<n;i++)
	{
		p[i]=i;
	}
	random_shuffle(p.begin(),p.end());
	while(1)
	{
		for(int i=0;i<k;i++) B[i]=def;
		set<int> bad;
		for(int i=0;i<n;i++)
		{
			grp[p[i]]=-1;
			for(int j=0;j<k;j++)
			{
				pair<ii,ii> tmp = inter(B[j],vec[p[i]]);
				if(tmp.fi.se<tmp.fi.fi||tmp.se.se<tmp.se.fi) continue;
				grp[p[i]]=j;
				B[j]=tmp;
				break;
			}
			if(grp[p[i]]==-1) bad.insert(p[i]);
		}
		if(bad.empty()) break;
		p.clear();
		for(int i=0;i<n;i++)
		{
			if(bad.find(i)==bad.end())
			{
				p.pb(i);
			}
		}
		random_shuffle(p.begin(),p.end());
		vi q;
		for(int x:bad)
		{
			q.pb(x);
		}
		random_shuffle(q.begin(),q.end());
		for(int x:q) p.pb(x);
		reverse(p.begin(),p.end());
	}
	for(int i=0;i<k;i++) getpt(i);
	for(ii x:ans)
	{
		cout<<x.fi<<' '<<x.se<<'\n';
	}
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:102:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for(int i=0;i<vec.size();i++)
      |              ~^~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 6 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79