Submission #212722

#	Time	Username	Problem	Language	Result	Execution time	Memory
212722		username	Hamburg Steak (JOI20_hamburg)	C++14	21 / 100	3060 ms	10632 KiB

hamburg

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(int i=j;i<k;++i)
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)

struct nd{
	int l,d,r,u;
};

const int maxn=2e5+9;
int n,p,pm[maxn];
vector<nd>a,b;
pii res[5];
bitset<maxn>vis;
mt19937 rd(time(0));

nd merge(nd x,nd y){
	return nd{max(x.l,y.l),max(x.d,y.d),min(x.r,y.r),min(x.u,y.u)};
}

main(){
	IOS;
	cin>>n>>p;
	REP(i,0,n){
		int l,d,r,u;cin>>l>>d>>r>>u;
		a.pb(nd{l,d,r,u});
	}
	while(1){
		vis.reset();
		REP(k,0,p){
			nd un=nd{1,1,1000000000,1000000000};
			REP(i,0,n){
				if(vis[i])continue;
				nd tt=merge(un,a[i]);
				if(tt.d<=tt.u&&tt.l<=tt.r){
					vis[i]=1;
					un=tt;
				}
			}
			res[k]={un.l,un.d};
		}
		iota(pm,pm+n,0);
		shuffle(pm,pm+n,rd);
		b.clear();
		REP(i,0,n){
			if(!vis[pm[i]]){
				b.pb(a[pm[i]]);
			}
		}
		if(b.empty()){
			REP(i,0,p)cout<<res[i].f<<" "<<res[i].s<<endl;
			return 0;
		}
		REP(i,0,n){
			if(vis[pm[i]]){
				b.pb(a[pm[i]]);
			}
		}
		a=b;
	}
}

Compilation message (stderr)

hamburg.cpp:26:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main(){
      |      ^

• 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