oj.uz

Submission #242013

# Submission time Handle Problem Language Result Execution time Memory
242013 2020-06-26T13:57:57 Z kostia244 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 474 ms 18088 KB 
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
const int inf = 1<<30, maxn = 1<<19;
using rc = array<int, 4>;
using pt = array<int, 2>;
int n, k;
vector<int> cx, cy;
bool isect(pt x, int y) {
	return x[0] <= y && y <= x[1];
}
bool isect(rc x, pt y) {
	return isect({x[0], x[2]}, y[0]) && isect({x[1], x[3]}, y[1]);
}
pt com(pt x, pt y) {
	return {max(x[0], y[0]), min(x[1], y[1])};
}
bool empty(pt x) {
	return x[0] > x[1];
}
rc bounds(vector<rc> r) {
	rc b = {0, 0, 3*n, 3*n};
	for(auto t : r)
		for(int j = 0; j < 4; j++)
			b[j] = (j < 2 ? max(b[j], t[j]) : min(b[j], t[j]));
	return b;
}
void suicide(vector<pt> r) {
	while(r.size() < k) r.push_back({1, 1});
	for(auto &i : r) cout << cx[i[0]] << " " << cy[i[1]] << '\n';
	exit(0);
}
pair<int, int> info(rc r, rc b) {
	int c = 0, e = 0;
	for(int i = 0; i < 4; i++) {
		e |= isect({r[0+(i&1)], r[2+(i&1)]}, b[i])<<i;
		c |= isect(r, {b[(i&1)*2], b[1+(i&2)]})<<i;
	}
	return {c, e};
}
vector<rc> split(vector<rc> r, pt f) {
	for(int i = r.size(); i--;) {
		if(isect(r[i], f)) swap(r[i], r.back()), r.pop_back();
	}
	return r;
}
multiset<int> Ll, Lr, Tl, Tr, Bl, Br;
vector<pt> Ts, Bs;
vector<pt> Ms, Mss, Msp;
map<int, vector<array<int, 3>>, greater<int>> ev;
void hell(vector<rc> r) {
	Ts.resize(maxn), Bs.resize(maxn);
	pt g = {-inf, inf};
	rc b = bounds(r);
	if(b[0] <= b[2] || b[1] <= b[3]) return;
	for(int i = 0; i < maxn; i++) Ts[i] = Bs[i] = {-inf, inf};
	for(auto &i : r) {
		for(int x = 0; x < 4; x++)
			for(int y = x&1; y < 4; y+=2)
				i[x] = y<2?min(i[x], b[y]):max(i[x], b[y]);
		auto [c, e] = info(i, b);
		if(c&(c-1)) continue;
		if(c == 1) {
			int lol = ev[i[1]].size();
			ev[i[1]-1].push_back({2, i[0], i[2]});
		} else if(c == 4) {
			assert(b[1] >= i[3]);
			ev[b[1]].push_back({3, i[0], i[2]});
			ev[i[3]].push_back({-3, i[0], i[2]});
		}  else if(c == 2 || c == 8) {
			if(c == 8) swap(Ts, Bs);
			Ts[i[0]-1] = com(Ts[i[0]-1], {i[1], i[3]});
			if(c == 8) swap(Ts, Bs);
		} else if(int c = isect({i[0], i[2]}, b[0])*2 + isect({i[0], i[2]}, b[2]); c) {
			if(c == 1) {
				Ll.insert(i[1]);
				Lr.insert(i[3]);
			} else if(c == 3) {
				assert(b[1] >= i[3]);
				ev[b[1]].push_back({1, i[1], i[3]});
				ev[i[3]].push_back({-1, i[1], i[3]});
				int lol = ev[i[1]].size();
				ev[i[1]-1].push_back({1, i[1], i[3]});
			} else
				g = com(g, {i[1], i[3]});
		} else if(int c = isect({i[1], i[3]}, b[1])*2 + isect({i[1], i[3]}, b[3]); c) {
			if(c == 3) {
				Ms.push_back({i[0], i[2]});
			} else {
				(c == 1 ? Bl : Tl).insert(i[0]);
				(c == 1 ? Br : Tr).insert(i[2]);
			}
		}
	}
	for(int i = 1; i < maxn; i++)
		Ts[i] = com(Ts[i], Ts[i-1]),
		Bs[i] = com(Bs[i], Bs[i-1]);
	sort(all(Ms));
	Mss = Msp = Ms;
	for(int i = 1; i < Ms.size(); i++) Msp[i] = com(Msp[i], Msp[i-1]);
	for(int i = (int)Ms.size()-1; i-- > 0;) Mss[i] = com(Mss[i+1], Mss[i]);
	int p, q;
	for(int moment = 3*n; moment--;) {
		for(auto [t, l, r] : ev[moment]) {
			#define CURl (t == 1 ? Ll : (t == 2 ? Tl : Bl))
			#define CURr (t == 1 ? Lr : (t == 2 ? Tr : Br))
			if(t > 0) {
				t = abs(t);
				CURl.insert(l);
				CURr.insert(r);
			} else {
				t = abs(t);
				assert(CURl.find(l) != CURl.end());
				assert(CURr.find(r) != CURr.end());
				CURl.erase(CURl.find(l));
				CURr.erase(CURr.find(r));
			}
		}
		
		for(int I = 2; I--;) {
			swap(Ts, Bs);
			swap(Tl, Bl), swap(Tr, Br);
			auto [sLl, sLr] = Ll.empty() ? pt{b[3], b[1]} : pt{*Ll.rbegin(), *Lr.begin()};
			auto [sTl, sTr] = Tl.empty() ? pt{b[2], b[0]} : pt{*Tl.rbegin(), *Tr.begin()};
			auto [sBl, sBr] = Bl.empty() ? pt{b[2], b[0]} : pt{*Bl.rbegin(), *Br.begin()};
			if(isect({g[0], g[1]}, moment) || sLl > sLr || sTl > sTr || sBl > sBr) continue;
			p = Ms.size();
			for(int i = 1<<19; i>>=1;)
			if(p-i >= 0 && !empty(com(Mss[p-i], {sTl, sTr}))) p -= i;
			if((p == 0 || !empty(com(Msp[p-1], {sBl, sBr}))) && !empty(com(Mss[p], {sTl, sTr}))) {
				pt br = com(Msp[p-1], {sBl, sBr});
				pt tr = com(Mss[p], {sTl, sTr});
				if(empty(br)||empty(tr)) continue;
				//cout << "GOT there " << sLl << " " << sLr << " " << Ts[tr[0]-1][0] << " " << Ts[tr[0]-1][1] << '\n';
				pt lr = com({sLl, sLr}, com(Ts[tr[0]-1], Bs[br[0]-1]));
				if(!empty(lr)) {
					vector<pt> ans;
					ans.push_back({b[0], moment});
					ans.push_back({tr[0], b[1]});
					ans.push_back({br[0], b[3]});
					ans.push_back({b[2], lr[0]});
					suicide(ans);
				}
				
			}
		}
	}
}
int K;
void gay(vector<rc> r, int k, vector<pt> ans) {
	if(r.empty() && ans.size() <= K) suicide(ans);
	if(k == 0) return;
	rc b = bounds(r);
	if(b[0] <= b[2] || b[1] <= b[3]) {
		int rev = 0;
		if(b[0] > b[2]) {
			swap(b[0], b[1]), swap(b[2], b[3]);
			for(auto &b : r)
				swap(b[0], b[1]), swap(b[2], b[3]);
			rev = 1;
		}
		vector<pt> segs;
		for(auto [l, d, r, u] : r) segs.push_back({d, u});
		sort(all(segs), greater<>());
		int c = inf;
		for(auto i : segs) {
			if(i[1] < c) {
				c = i[0];
				ans.push_back(rev ? pt{i[0], b[0]} : pt{b[0], i[0]});
			}
		}
		if(ans.size() <= K)
			suicide(ans);
		if(rev) {
			swap(b[0], b[1]), swap(b[2], b[3]);
			for(auto &b : r)
				swap(b[0], b[1]), swap(b[2], b[3]); 
		}
	}
	for(int i = 0; i < 4; i++) {
		pt P {b[2*(i&1)], b[1 + (i&2)]};
		ans.push_back(P);
		gay(split(r, P), k-1, ans);
		ans.pop_back();
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> k;
	K = k;
	vector<rc> r(n);
	cx = cy = {-inf, inf};
	for(auto &i : r)
		for(int j = 0; j < 4; j++) cin >> i[j], (j%2 ? cy : cx).push_back(i[j]);
	for(auto *i : {&cx, &cy})
		sort(i->begin(), i->end());
	for(auto &i : r)
		for(int j = 0; j < 4; j++) {
			i[j] = lower_bound(all(cx), i[j]) - cx.begin();
			swap(cx, cy);
		}
	if(k == 4) hell(r);
	gay(r, k, {});
	return 0;
}

Compilation message

hamburg.cpp: In function 'void suicide(std::vector<std::array<int, 2> >)':
hamburg.cpp:29:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |  while(r.size() < k) r.push_back({1, 1});
      |        ~~~~~~~~~^~~
hamburg.cpp: In function 'void hell(std::vector<std::array<int, 4> >)':
hamburg.cpp:64:8: warning: unused variable 'lol' [-Wunused-variable]
   64 |    int lol = ev[i[1]].size();
      |        ^~~
hamburg.cpp:82:9: warning: unused variable 'lol' [-Wunused-variable]
   82 |     int lol = ev[i[1]].size();
      |         ^~~
hamburg.cpp:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i = 1; i < Ms.size(); i++) Msp[i] = com(Msp[i], Msp[i-1]);
      |                 ~~^~~~~~~~~~~
hamburg.cpp:102:9: warning: unused variable 'q' [-Wunused-variable]
  102 |  int p, q;
      |         ^
hamburg.cpp: In function 'void gay(std::vector<std::array<int, 4> >, int, std::vector<std::array<int, 2> >)':
hamburg.cpp:151:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  151 |  if(r.empty() && ans.size() <= K) suicide(ans);
      |                  ~~~~~~~~~~~^~~~
hamburg.cpp:172:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  172 |   if(ans.size() <= K)
      |      ~~~~~~~~~~~^~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8704 KB Output is correct
2 Correct 9 ms 8704 KB Output is correct
3 Correct 8 ms 8704 KB Output is correct
4 Correct 9 ms 8704 KB Output is correct
5 Correct 8 ms 8704 KB Output is correct
6 Correct 8 ms 8704 KB Output is correct
7 Correct 20 ms 9268 KB Output is correct
8 Correct 25 ms 9312 KB Output is correct
9 Correct 20 ms 9216 KB Output is correct
10 Correct 21 ms 9208 KB Output is correct
11 Correct 25 ms 9216 KB Output is correct
12 Correct 20 ms 9216 KB Output is correct
13 Correct 20 ms 9216 KB Output is correct
14 Incorrect 22 ms 9216 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 382 ms 13356 KB Output is correct
6 Correct 370 ms 13476 KB Output is correct
7 Correct 373 ms 13344 KB Output is correct
8 Correct 368 ms 13376 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 377 ms 14672 KB Output is correct
6 Correct 396 ms 14632 KB Output is correct
7 Correct 343 ms 14628 KB Output is correct
8 Correct 372 ms 15136 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 371 ms 13404 KB Output is correct
14 Correct 349 ms 13348 KB Output is correct
15 Correct 358 ms 13344 KB Output is correct
16 Correct 350 ms 13352 KB Output is correct
17 Correct 415 ms 13468 KB Output is correct
18 Correct 361 ms 13344 KB Output is correct
19 Correct 372 ms 15296 KB Output is correct
20 Correct 439 ms 18088 KB Output is correct
21 Correct 370 ms 15832 KB Output is correct
22 Correct 474 ms 17956 KB Output is correct
23 Correct 422 ms 17876 KB Output is correct
24 Correct 413 ms 17328 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8704 KB Output is correct
2 Correct 9 ms 8704 KB Output is correct
3 Correct 8 ms 8704 KB Output is correct
4 Correct 9 ms 8704 KB Output is correct
5 Correct 8 ms 8704 KB Output is correct
6 Correct 8 ms 8704 KB Output is correct
7 Correct 20 ms 9268 KB Output is correct
8 Correct 25 ms 9312 KB Output is correct
9 Correct 20 ms 9216 KB Output is correct
10 Correct 21 ms 9208 KB Output is correct
11 Correct 25 ms 9216 KB Output is correct
12 Correct 20 ms 9216 KB Output is correct
13 Correct 20 ms 9216 KB Output is correct
14 Incorrect 22 ms 9216 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -