Submission #303970

#	Time	Username	Problem	Language	Result	Execution time	Memory
303970		Pajaraja	Hamburg Steak (JOI20_hamburg)	C++17	12 / 100	3089 ms	6648 KiB

hamburg

#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;
int n,k;
struct rect{int xl,xh,yl,yh;};
rect intersect(rect a,rect b) {rect r={max(a.xl,b.xl),min(a.xh,b.xh),max(a.yl,b.yl),min(a.yh,b.yh)}; return r;}
bool valid(rect a) {return a.xh>=a.xl && a.yh>=a.yl;}
rect p[MAXN],res;
pair<int,int> px[MAXN],py[MAXN];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline vector<rect> check(vector<rect> pot)
{
	vector<rect> t;
	for(int i=0;i<n;i++)
	{
		bool ziv=false;
		for(int j=0;j<pot.size();j++) if(valid(intersect(p[i],pot[j]))) 
		{
			pot[j]=intersect(pot[j],p[i]);
			ziv=true;
			break;
		}
		if(!ziv) return t;
	}
	return pot;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d%d%d",&p[i].xl,&p[i].yl,&p[i].xh,&p[i].yh);
		if(!i) res=intersect(p[0],p[0]);
		else res=intersect(res,p[i]);
	}
	if(k==1) {printf("%d %d",res.xl,res.yl); return 0;}
	if(k>1 && valid(res))
	{
		printf("%d %d\n",res.xl,res.yl);
		for(int i=1;i<k;i++) printf("1 1\n");
		return 0;
	}
	for(int i=0;i<n;i++) px[i]={p[i].xl,p[i].xh};
	for(int i=0;i<n;i++) py[i]={p[i].yl,p[i].yh};
	sort(px,px+n);
	sort(py,py+n);
	vector<int> xn,yn;
	int mnx=1000000007,mndx,mny=1000000007,mndy;
	for(int i=0;i<n;i++)
	{
		if(mnx>=px[i].second) 
		{
			mnx=px[i].second;
			mndx=i;
		}
		if(px[i].first>mnx)
		{
			xn.push_back(mndx);
			mnx=px[i].second;
			mndx=i;
		}
	}
	xn.push_back(mndx);
	for(int i=0;i<n;i++)
	{
		if(mny>=py[i].second) 
		{
			mny=py[i].second;
			mndy=i;
		}
		if(py[i].first>mny)
		{
			yn.push_back(mndy);
			mny=py[i].second;
			mndy=i;
		}
	}
	yn.push_back(mndy);
	while(xn.size()>yn.size()) yn.push_back(yn[0]);
	while(yn.size()>xn.size()) xn.push_back(xn[0]);
	int t=xn.size();
	sort(xn.begin(),xn.end());
	sort(yn.begin(),yn.end());
	while(true)
	{
		do
		{
			vector<rect> prv;
			for(int i=0;i<t;i++) prv.push_back({px[xn[i]].first,px[xn[i]].second,py[yn[i]].first,py[yn[i]].second});
			vector<rect> sol=check(prv);
			if(sol.size()!=0)
			{
				for(int i=0;i<t;i++) printf("%d %d\n",sol[i].xl,sol[i].yl);
				for(int i=t;i<k;i++) printf("1 1\n");
				return 0;
			}
		} while(next_permutation(yn.begin(),yn.end()));
		shuffle(p,p+n,rng);
	}
}

Compilation message (stderr)

hamburg.cpp: In function 'std::vector<rect> check(std::vector<rect>)':
hamburg.cpp:17:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for(int j=0;j<pot.size();j++) if(valid(intersect(p[i],pot[j])))
      |               ~^~~~~~~~~~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
hamburg.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   scanf("%d%d%d%d",&p[i].xl,&p[i].yl,&p[i].xh,&p[i].yh);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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