oj.uz

Submission #217262

# Submission time Handle Problem Language Result Execution time Memory
217262 2020-03-29T10:30:04 Z Toadologist Hamburg Steak (JOI20_hamburg) C++11
15 / 100
 376 ms 13308 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << a[qwq];\
		else cerr << ", " << a[qwq];\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }
template<typename A, typename B>
ostream& operator << (ostream& out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}

const int maxN = 200000 + 5;
struct Rect {
	int L, D, R, U;
	Rect(int l, int d, int r, int u) : L(l), D(d), R(r), U(u) {}
	LL area() const {
		return (LL)max(0, R - L + 1) * (LL)max(0, U - D + 1);
	}
	bool hit(pii p) const {
		return L <= p.first && p.first <= R && D <= p.second && p.second <= U;
	}
};
int nx, ny;
vector<int> tx, ty;

Rect com(Rect x, Rect y) {
	return Rect(max(x.L, y.L), max(x.D, y.D), min(x.R, y.R), min(x.U, y.U));
}

void disc(vector<Rect> &v) {
	{
	vector<int> &t = tx;
	t.clear();
	for(auto r : v) t.push_back(r.L), t.push_back(r.R);
	sort(t.begin(), t.end());
	t.erase(unique(t.begin(), t.end()), t.end());
	for(auto &r : v)
		r.L = lower_bound(t.begin(), t.end(), r.L) - t.begin() + 1,
		r.R = lower_bound(t.begin(), t.end(), r.R) - t.begin() + 1;
	nx = t.size();
	}
	{
	vector<int> &t = ty;
	t.clear();
	for(auto r : v) t.push_back(r.D), t.push_back(r.U);
	sort(t.begin(), t.end());
	t.erase(unique(t.begin(), t.end()), t.end());
	for(auto &r : v)
		r.D = lower_bound(t.begin(), t.end(), r.D) - t.begin() + 1,
		r.U = lower_bound(t.begin(), t.end(), r.U) - t.begin() + 1;
	ny = t.size();
	}
}

vector<Rect> ans;

vector<int> oned(vector<pii> &v) {
	displayv(v);
	vector<int> res;
	sort(v.begin(), v.end());
	int last = max(nx, ny) + 1;
	for(int i = (int)v.size() - 1; i >= 0; --i) {
		if(v[i].first <= last && last <= v[i].second) continue;
		else res.push_back(last = v[i].first);
	}
	displayv(res);
	return res;
}

bool solve(vector<Rect> &v, int k, vector<pii> &res) {
	res.clear();
	{ // k == 0
		if(v.size() == 0) return true;
		if(k <= 0) return false;
	}
	
	Rect c(1, 1, nx, ny);
	for(auto r : v) c = com(c, r);
	{ // k == 1
		if(c.area() > 0) {
			res.emplace_back(c.L, c.D);
			return true;
		}
		if(k <= 1) return false;
	}
	if(c.L <= c.R) {
		vector<pii> segs;
		for(int i = 0; i < (int)v.size(); ++i)
			segs.emplace_back(v[i].D, v[i].U);
		vector<int> pos = oned(segs);
		if((int)pos.size() > k) return false;
		
		for(auto p : pos) res.emplace_back(c.L, p);
		return true;
	}
	if(c.D <= c.U) {
		vector<pii> segs;
		for(int i = 0; i < (int)v.size(); ++i)
			segs.emplace_back(v[i].L, v[i].R);
		vector<int> pos = oned(segs);
		if((int)pos.size() > k) return false;
		
		for(auto p : pos) res.emplace_back(p, c.D);
		return true;
	}
	{ // k == 2
		auto check = [&](pii x, pii y) {
			for(auto r : v) {
				if(!r.hit(x) && !r.hit(y)) {
					return false;
				}
			}
			res.push_back(x);
			res.push_back(y);
			return true;
		};
		if(check(pii(c.L, c.D), pii(c.R, c.U))) return true;
		if(check(pii(c.L, c.U), pii(c.R, c.D))) return true;
		if(k <= 2) return false;
	}
	{ // k == 3
		auto check = [&](pii x) {
			vector<Rect> nv;
			vector<pii> sol;
			for(auto r : v) {
				if(!r.hit(x)) nv.push_back(r);
			}
			if(solve(nv, k - 1, sol)) {
				res.push_back(x);
				res.insert(res.end(), sol.begin(), sol.end());
				return true;
			}
			return false;
		};
		if(check(pii(c.L, c.D))) return true;
		if(check(pii(c.L, c.U))) return true;
		if(check(pii(c.R, c.D))) return true;
		if(check(pii(c.R, c.U))) return true;
		if(k <= 3) return false;
	}
	{
	}
	return false;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
#endif
	int n, k;
	cin >> n >> k;
	vector<Rect> v;
	for(int i = 0; i < n; ++i) {
		int l, d, r, u;
		cin >> l >> d >> r >> u;
		v.emplace_back(l, d, r, u);
	}
	disc(v);
	for(auto r : v) eprintf("rect %d %d %d %d\n", r.L, r.D, r.R, r.U);
	
	vector<pii> res;
	bool ok = solve(v, k, res);
	assert(ok);
	while((int)res.size() < k) res.emplace_back(1, 1);
	for(auto p : res) cout << tx[p.first - 1] << " " << ty[p.second - 1] << endl;
	return 0;
}

Compilation message

hamburg.cpp: In function 'int main()':
hamburg.cpp:176:11: warning: variable 'r' set but not used [-Wunused-but-set-variable]
  176 |  for(auto r : v) eprintf("rect %d %d %d %d\n", r.L, r.D, r.R, r.U);
      |           ^

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 3 ms 404 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Runtime error 4 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 324 ms 8768 KB Output is correct
6 Correct 318 ms 8660 KB Output is correct
7 Correct 324 ms 8824 KB Output is correct
8 Correct 329 ms 8688 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 330 ms 8676 KB Output is correct
6 Correct 317 ms 8792 KB Output is correct
7 Correct 319 ms 8672 KB Output is correct
8 Correct 304 ms 8672 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 349 ms 10236 KB Output is correct
14 Correct 376 ms 10256 KB Output is correct
15 Correct 330 ms 10228 KB Output is correct
16 Correct 341 ms 10184 KB Output is correct
17 Correct 333 ms 10208 KB Output is correct
18 Correct 331 ms 10204 KB Output is correct
19 Correct 322 ms 12768 KB Output is correct
20 Correct 326 ms 13308 KB Output is correct
21 Correct 319 ms 12896 KB Output is correct
22 Correct 306 ms 13288 KB Output is correct
23 Correct 330 ms 13180 KB Output is correct
24 Correct 332 ms 12948 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 3 ms 404 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Runtime error 4 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -