Submission #716884

#	Time	Username	Problem	Language	Result	Execution time	Memory
716884		Dan4Life	Hamburg Steak (JOI20_hamburg)	C++17	21 / 100	3041 ms	20672 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define ar array

const int mxN=2e5;
int n, k, d[mxN], b[mxN];
ar<int, 4> a[mxN], p[4];
ar<int, 4> ir{1, 1, INT_MAX, INT_MAX};
vector<int> v1, v2;

ar<int, 4> it(ar<int, 4> a, ar<int, 4> b) {
	return {max(a[0], b[0]), max(a[1], b[1]), min(a[2], b[2]), min(a[3], b[3])};
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    //uniform_int_distribution<long long>(L, R)(rng);
    cin >> n >> k;
    for(int i=0; i<n; ++i) {
		cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
		v2.push_back(i);
	}
    while(1){
        vector<int> u=v2;
		v2.clear();
		for(int i=0; i<k; ++i)
			p[i]=ir;
		for(int i=0; i<n; ++i) {
			bool ok=0;
			for(int j=0; j<k; ++j) {
				ar<int, 4> bl=it(p[j], a[u[i]]);
				if(bl[0]<=bl[2]&&bl[1]<=bl[3]) {
					p[j]=bl;
					v1.push_back(u[i]);
					ok=1;
					break;
				}
			}
			if(!ok)
				v2.push_back(u[i]);
		}
		if(v2.empty()) {
			for(int j=0; j<k; ++j)
				cout << p[j][0] << " " << p[j][1] << "\n";
			break;
		}
		shuffle(all(v2),rng);
		v2.insert(v2.end(), all(v1));
		v1.clear();
    }
}

• 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