oj.uz

Submission #258872

# Submission time Handle Problem Language Result Execution time Memory
258872 2020-08-06T16:14:53 Z amoo_safar Hamburg Steak (JOI20_hamburg) C++14
100 / 100
 2541 ms 351396 KB 
// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

const ll Mod = 1000000007LL;
const int N = 8e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int n, k;
int L[N], R[N], U[N], D[N];

vector<int> uX, uY;
vector<pii> points;

void Done(){
	while((int) points.size() < k) points.pb(pii(0, 0));
	for(auto x : points) printf("%d %d\n", uX[x.F], uY[x.S]);
	exit(0);
}

int mk[N];
bool In(pii P, int id){
	return L[id] <= P.F && P.F <= R[id] && D[id] <= P.S && P.S <= U[id];
}
void On(pii P, int col){
	for(int i = 0; i < n; i++){
		if(L[i] <= P.F && P.F <= R[i] && D[i] <= P.S && P.S <= U[i] && !mk[i]) mk[i] = col;
	}
	points.pb(P);
}
void Off(int col){
	for(int i = 0; i < n; i++)
		if(mk[i] == col)
			mk[i] = 0;
	points.pop_back();
}

void Solve(int y){
	if(y == 0){
		for(int i = 0; i < n; i++)
			if(!mk[i])
				return ;
	}
	int mnx = N, mxx = -1;
	for(int i = 0; i < n; i++)
		if(!mk[i])
			mnx = min(mnx, R[i]), mxx = max(mxx, L[i]);
	if(mxx == -1){
		for(int i = 0; i < y; i++) points.pb(pii(0, 0));
		Done();
	}


	int mny = N, mxy = -1;
	for(int i = 0; i < n; i++)
		if(!mk[i])
			mny = min(mny, U[i]), mxy = max(mxy, D[i]);
	
	for(int px : {mnx, mxx}){
		for(int py : {mny, mxy}){
			On({px, py}, y);
			Solve(y - 1);
			Off(y);
		}
	}
}

const int N2 = N * 4;
vector<int> O[N2], I[N2];
void AddE(int u, int v){
	O[u].pb(v);
	I[v].pb(u);
}
void AddC(int u, int v){
	//if(u == v);
	AddE(u ^ 1, v);
	AddE(v ^ 1, u);
}
void Ban(int u, int v){
	AddC(u ^ 1, v ^ 1);
}

int mark[N2];
vector<int> top;
void DFS(int u){
	mark[u] = 1;
	for(auto adj : O[u]) if(!mark[adj]) DFS(adj);
	top.pb(u);
}

void DFS(int u, int c){
	mark[u] = c;
	for(auto adj : I[u]) if(!mark[adj]) DFS(adj, c);
}

bool isst[N2];

void Main(){

	int mnx = N2, mxx = -1;
	for(int i = 0; i < n; i++)
		if(!mk[i])
			mnx = min(mnx, R[i]), mxx = max(mxx, L[i]);
	int mny = N2, mxy = -1;
	for(int i = 0; i < n; i++)
		if(!mk[i])
			mny = min(mny, U[i]), mxy = max(mxy, D[i]);
	
	vector<pii> po;
	vector<int> ln;
	{ // Nodes
		int st = 0;
		for(int i = mnx + 1; i < mxx; i++)
			po.pb({i, mny});	
		
		isst[st] = true;
		for(int i = st; i + 1 < (int) po.size(); i++)
			Ban(i << 1 | 1, (i + 1) << 1);
		st = po.size();
		/////////////////////
		for(int i = mnx + 1; i < mxx; i++)
			po.pb({i, mxy});

		isst[st] = true;
		for(int i = st; i + 1 < (int) po.size(); i++)
			Ban(i << 1 | 1, (i + 1) << 1);
		st = po.size();
		/////////////////////
		for(int i = mny + 1; i < mxy; i++)
			po.pb({mnx, i});	
		
		isst[st] = true;
		for(int i = st; i + 1 < (int) po.size(); i++)
			Ban(i << 1 | 1, (i + 1) << 1);
		st = po.size();
		/////////////////////
		for(int i = mny + 1; i < mxy; i++)
			po.pb({mxx, i});

		isst[st] = true;
		for(int i = st; i + 1 < (int) po.size(); i++)
			Ban(i << 1 | 1, (i + 1) << 1);
		st = po.size();
	}
	int m = po.size();
	for(int i = 0; i < m; i++) if(isst[i]) ln.pb(i);
	ln.pb(m);
	assert(ln.size() == 5);
	assert(2 * m < N2);
	int fst, la;
	vector<pii> seg;
	for(int i = 0; i < n; i++){
		seg.clear();
		/*for(int j = 0; j < 4; j++){
			fst = -1; la = -1;
			for(int l = ln[j]; l < ln[j + 1]; l++){
				if(In(po[l], i)){
					la = l;
					if(fst == -1) fst = l;
				}
			}

			if(fst == -1) continue;
			seg.pb({fst, la});
		}
		*/
		// 1
		if(D[i] <= mny){
			fst = max(mnx + 1, L[i]) - (mnx + 1);
			la = min(mxx - 1, R[i]) - (mnx + 1);
			if(fst <= la) seg.pb(pii(fst + ln[0], la + ln[0]));
		}
		// 2
		if(U[i] >= mxy){
			fst = max(mnx + 1, L[i]) - (mnx + 1);
			la = min(mxx - 1, R[i]) - (mnx + 1);
			if(fst <= la) seg.pb(pii(fst + ln[1], la + ln[1]));
		}
		// 3
		if(L[i] <= mnx){
			fst = max(mny + 1, D[i]) - (mny + 1);
			la = min(mxy - 1, U[i]) - (mny + 1);
			if(fst <= la) seg.pb(pii(fst + ln[2], la + ln[2]));
		}
		// 4
		if(R[i] >= mxx){
			fst = max(mny + 1, D[i]) - (mny + 1);
			la = min(mxy - 1, U[i]) - (mny + 1);
			if(fst <= la) seg.pb(pii(fst + ln[3], la + ln[3]));
		}


		if(seg.empty() || seg.size() > 2) continue;
		if(seg.size() == 1){
			AddC(seg[0].S << 1 | 1, seg[0].S << 1 | 1);
			if(!isst[seg[0].F])
				AddC((seg[0].F - 1) << 1, (seg[0].F - 1) << 1);
		} else {
			vector<int> B[2];
			for(int j = 0; j < 2; j++){
				B[j].pb(seg[j].S << 1 | 0);
				if(!isst[seg[j].F])
					B[j].pb((seg[j].F - 1) << 1 | 1);
			}
			for(int b1 : B[0]) for(int b2 : B[1]) Ban(b1, b2);
		}
	}

	for(int i = 0; i < m + m; i++){
		if(!mark[i]) DFS(i);
	}
	reverse(all(top));
	memset(mark, 0, sizeof mark);
	int cnt = 1;
	for(auto x : top) if(!mark[x]){
		DFS(x, cnt);
		cnt ++;
	}
	vector<int> val(m, 0);
	for(int i = 0; i < m; i++)
		val[i] = (mark[i + i] < mark[i + i + 1] ? 1 : 0);

	for(int j = 0; j < 4; j++){
		for(int l = ln[j]; l < ln[j + 1]; l++){
			if(val[l]){
				points.pb(po[l]);
				break;
			}
		}
	}
	Done();
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n; i++) scanf("%d%d%d%d", L + i, D + i, R + i, U + i);

	for(int i = 0; i < n; i++) uX.pb(L[i]), uY.pb(D[i]), uX.pb(R[i]), uY.pb(U[i]);
	
	sort(all(uX)); uX.resize(unique(all(uX)) - uX.begin());
	sort(all(uY)); uY.resize(unique(all(uY)) - uY.begin());

	for(int i = 0; i < n; i++){
		L[i] = lower_bound(all(uX), L[i]) - uX.begin();
		R[i] = lower_bound(all(uX), R[i]) - uX.begin();
		U[i] = lower_bound(all(uY), U[i]) - uY.begin();
		D[i] = lower_bound(all(uY), D[i]) - uY.begin();
	}

	//assert(k <= 3);

	Solve(k);
	assert(k == 4);
	Main();

	return 0;
}

/*
4 4
1 4 1 4
2 1 2 1
3 0 3 0
4 3 4 3

*/

Compilation message

hamburg.cpp: In function 'int main()':
hamburg.cpp:250:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  250 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:251:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  251 |  for(int i = 0; i < n; i++) scanf("%d%d%d%d", L + i, D + i, R + i, U + i);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 150772 KB Output is correct
2 Correct 126 ms 150776 KB Output is correct
3 Correct 116 ms 150780 KB Output is correct
4 Correct 117 ms 150776 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 150904 KB Output is correct
2 Correct 117 ms 150728 KB Output is correct
3 Correct 117 ms 150776 KB Output is correct
4 Correct 123 ms 150776 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 150716 KB Output is correct
2 Correct 119 ms 150932 KB Output is correct
3 Correct 121 ms 150820 KB Output is correct
4 Correct 117 ms 150708 KB Output is correct
5 Correct 115 ms 150776 KB Output is correct
6 Correct 125 ms 150744 KB Output is correct
7 Correct 119 ms 150820 KB Output is correct
8 Correct 114 ms 150776 KB Output is correct
9 Correct 116 ms 150776 KB Output is correct
10 Correct 130 ms 150776 KB Output is correct
11 Correct 121 ms 150776 KB Output is correct
12 Correct 122 ms 150840 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 150756 KB Output is correct
2 Correct 120 ms 150776 KB Output is correct
3 Correct 110 ms 150792 KB Output is correct
4 Correct 124 ms 150776 KB Output is correct
5 Correct 114 ms 150712 KB Output is correct
6 Correct 114 ms 150776 KB Output is correct
7 Correct 123 ms 150776 KB Output is correct
8 Correct 117 ms 150708 KB Output is correct
9 Correct 119 ms 150816 KB Output is correct
10 Correct 122 ms 150940 KB Output is correct
11 Correct 128 ms 150740 KB Output is correct
12 Correct 115 ms 150776 KB Output is correct
13 Correct 128 ms 150716 KB Output is correct
14 Correct 145 ms 164292 KB Output is correct
15 Correct 127 ms 150704 KB Output is correct
16 Correct 125 ms 150732 KB Output is correct
17 Correct 144 ms 164396 KB Output is correct
18 Correct 117 ms 150776 KB Output is correct
19 Correct 126 ms 150828 KB Output is correct
20 Correct 150 ms 164668 KB Output is correct
21 Correct 122 ms 150776 KB Output is correct
22 Correct 124 ms 150776 KB Output is correct
23 Correct 138 ms 164772 KB Output is correct
24 Correct 118 ms 150824 KB Output is correct
25 Correct 121 ms 150776 KB Output is correct
26 Correct 125 ms 150776 KB Output is correct
27 Correct 122 ms 150800 KB Output is correct
28 Correct 116 ms 150752 KB Output is correct
29 Correct 130 ms 150776 KB Output is correct
30 Correct 118 ms 150904 KB Output is correct
31 Correct 136 ms 164300 KB Output is correct
32 Correct 139 ms 164100 KB Output is correct
33 Correct 134 ms 164380 KB Output is correct
34 Correct 137 ms 164216 KB Output is correct
35 Correct 137 ms 164760 KB Output is correct
36 Correct 136 ms 164216 KB Output is correct
37 Correct 137 ms 165012 KB Output is correct
38 Correct 135 ms 165180 KB Output is correct
39 Correct 138 ms 164472 KB Output is correct
40 Correct 134 ms 164344 KB Output is correct
41 Correct 128 ms 164472 KB Output is correct
42 Correct 129 ms 164472 KB Output is correct
43 Correct 135 ms 164600 KB Output is correct
44 Correct 130 ms 164600 KB Output is correct
45 Correct 114 ms 150776 KB Output is correct
46 Correct 130 ms 164728 KB Output is correct
47 Correct 133 ms 164600 KB Output is correct
48 Correct 135 ms 164988 KB Output is correct
49 Correct 147 ms 164600 KB Output is correct
50 Correct 132 ms 164476 KB Output is correct
51 Correct 131 ms 164856 KB Output is correct
52 Correct 134 ms 164344 KB Output is correct
53 Correct 139 ms 164472 KB Output is correct
54 Correct 145 ms 164984 KB Output is correct
55 Correct 142 ms 164472 KB Output is correct
56 Correct 133 ms 164520 KB Output is correct
57 Correct 130 ms 164388 KB Output is correct
58 Correct 134 ms 164472 KB Output is correct

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 150772 KB Output is correct
2 Correct 126 ms 150776 KB Output is correct
3 Correct 116 ms 150780 KB Output is correct
4 Correct 117 ms 150776 KB Output is correct
5 Correct 516 ms 158032 KB Output is correct
6 Correct 540 ms 158008 KB Output is correct
7 Correct 482 ms 157904 KB Output is correct
8 Correct 475 ms 157940 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 150904 KB Output is correct
2 Correct 117 ms 150728 KB Output is correct
3 Correct 117 ms 150776 KB Output is correct
4 Correct 123 ms 150776 KB Output is correct
5 Correct 464 ms 157996 KB Output is correct
6 Correct 513 ms 158120 KB Output is correct
7 Correct 470 ms 157904 KB Output is correct
8 Correct 565 ms 157908 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 150716 KB Output is correct
2 Correct 119 ms 150932 KB Output is correct
3 Correct 121 ms 150820 KB Output is correct
4 Correct 117 ms 150708 KB Output is correct
5 Correct 115 ms 150776 KB Output is correct
6 Correct 125 ms 150744 KB Output is correct
7 Correct 119 ms 150820 KB Output is correct
8 Correct 114 ms 150776 KB Output is correct
9 Correct 116 ms 150776 KB Output is correct
10 Correct 130 ms 150776 KB Output is correct
11 Correct 121 ms 150776 KB Output is correct
12 Correct 122 ms 150840 KB Output is correct
13 Correct 518 ms 158048 KB Output is correct
14 Correct 489 ms 158164 KB Output is correct
15 Correct 491 ms 158056 KB Output is correct
16 Correct 513 ms 157912 KB Output is correct
17 Correct 501 ms 157904 KB Output is correct
18 Correct 517 ms 157992 KB Output is correct
19 Correct 517 ms 157912 KB Output is correct
20 Correct 501 ms 157932 KB Output is correct
21 Correct 671 ms 158012 KB Output is correct
22 Correct 682 ms 158128 KB Output is correct
23 Correct 540 ms 157988 KB Output is correct
24 Correct 540 ms 157908 KB Output is correct

Subtask #8
79.0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 150756 KB Output is correct
2 Correct 120 ms 150776 KB Output is correct
3 Correct 110 ms 150792 KB Output is correct
4 Correct 124 ms 150776 KB Output is correct
5 Correct 114 ms 150712 KB Output is correct
6 Correct 114 ms 150776 KB Output is correct
7 Correct 123 ms 150776 KB Output is correct
8 Correct 117 ms 150708 KB Output is correct
9 Correct 119 ms 150816 KB Output is correct
10 Correct 122 ms 150940 KB Output is correct
11 Correct 128 ms 150740 KB Output is correct
12 Correct 115 ms 150776 KB Output is correct
13 Correct 128 ms 150716 KB Output is correct
14 Correct 145 ms 164292 KB Output is correct
15 Correct 127 ms 150704 KB Output is correct
16 Correct 125 ms 150732 KB Output is correct
17 Correct 144 ms 164396 KB Output is correct
18 Correct 117 ms 150776 KB Output is correct
19 Correct 126 ms 150828 KB Output is correct
20 Correct 150 ms 164668 KB Output is correct
21 Correct 122 ms 150776 KB Output is correct
22 Correct 124 ms 150776 KB Output is correct
23 Correct 138 ms 164772 KB Output is correct
24 Correct 118 ms 150824 KB Output is correct
25 Correct 121 ms 150776 KB Output is correct
26 Correct 125 ms 150776 KB Output is correct
27 Correct 122 ms 150800 KB Output is correct
28 Correct 116 ms 150752 KB Output is correct
29 Correct 130 ms 150776 KB Output is correct
30 Correct 118 ms 150904 KB Output is correct
31 Correct 136 ms 164300 KB Output is correct
32 Correct 139 ms 164100 KB Output is correct
33 Correct 134 ms 164380 KB Output is correct
34 Correct 137 ms 164216 KB Output is correct
35 Correct 137 ms 164760 KB Output is correct
36 Correct 136 ms 164216 KB Output is correct
37 Correct 137 ms 165012 KB Output is correct
38 Correct 135 ms 165180 KB Output is correct
39 Correct 138 ms 164472 KB Output is correct
40 Correct 134 ms 164344 KB Output is correct
41 Correct 128 ms 164472 KB Output is correct
42 Correct 129 ms 164472 KB Output is correct
43 Correct 135 ms 164600 KB Output is correct
44 Correct 130 ms 164600 KB Output is correct
45 Correct 114 ms 150776 KB Output is correct
46 Correct 130 ms 164728 KB Output is correct
47 Correct 133 ms 164600 KB Output is correct
48 Correct 135 ms 164988 KB Output is correct
49 Correct 147 ms 164600 KB Output is correct
50 Correct 132 ms 164476 KB Output is correct
51 Correct 131 ms 164856 KB Output is correct
52 Correct 134 ms 164344 KB Output is correct
53 Correct 139 ms 164472 KB Output is correct
54 Correct 145 ms 164984 KB Output is correct
55 Correct 142 ms 164472 KB Output is correct
56 Correct 133 ms 164520 KB Output is correct
57 Correct 130 ms 164388 KB Output is correct
58 Correct 134 ms 164472 KB Output is correct
59 Correct 500 ms 158064 KB Output is correct
60 Correct 508 ms 158000 KB Output is correct
61 Correct 487 ms 157912 KB Output is correct
62 Correct 482 ms 157912 KB Output is correct
63 Correct 505 ms 158016 KB Output is correct
64 Correct 491 ms 157888 KB Output is correct
65 Correct 511 ms 157924 KB Output is correct
66 Correct 482 ms 157912 KB Output is correct
67 Correct 705 ms 158032 KB Output is correct
68 Correct 630 ms 157908 KB Output is correct
69 Correct 548 ms 158004 KB Output is correct
70 Correct 566 ms 158060 KB Output is correct
71 Correct 1425 ms 157908 KB Output is correct
72 Correct 2365 ms 316708 KB Output is correct
73 Correct 1298 ms 158012 KB Output is correct
74 Correct 926 ms 158040 KB Output is correct
75 Correct 1972 ms 276268 KB Output is correct
76 Correct 974 ms 158060 KB Output is correct
77 Correct 1220 ms 158012 KB Output is correct
78 Correct 2404 ms 347824 KB Output is correct
79 Correct 1369 ms 157912 KB Output is correct
80 Correct 1163 ms 157992 KB Output is correct
81 Correct 2372 ms 328224 KB Output is correct
82 Correct 1078 ms 158036 KB Output is correct
83 Correct 737 ms 158072 KB Output is correct
84 Correct 748 ms 157892 KB Output is correct
85 Correct 852 ms 157912 KB Output is correct
86 Correct 830 ms 157944 KB Output is correct
87 Correct 751 ms 157980 KB Output is correct
88 Correct 824 ms 157896 KB Output is correct
89 Correct 2162 ms 300452 KB Output is correct
90 Correct 2427 ms 341136 KB Output is correct
91 Correct 2248 ms 302200 KB Output is correct
92 Correct 2359 ms 346252 KB Output is correct
93 Correct 2403 ms 320292 KB Output is correct
94 Correct 2509 ms 323240 KB Output is correct
95 Correct 2420 ms 332140 KB Output is correct
96 Correct 2261 ms 305356 KB Output is correct
97 Correct 2355 ms 321948 KB Output is correct
98 Correct 2541 ms 316516 KB Output is correct
99 Correct 2080 ms 293072 KB Output is correct
100 Correct 2397 ms 337448 KB Output is correct
101 Correct 2333 ms 335904 KB Output is correct
102 Correct 1966 ms 262604 KB Output is correct
103 Correct 2400 ms 347744 KB Output is correct
104 Correct 2058 ms 284320 KB Output is correct
105 Correct 2330 ms 351396 KB Output is correct
106 Correct 2466 ms 333472 KB Output is correct
107 Correct 2214 ms 303888 KB Output is correct
108 Correct 2437 ms 341248 KB Output is correct
109 Correct 2444 ms 346636 KB Output is correct
110 Correct 2358 ms 332204 KB Output is correct
111 Correct 2520 ms 317484 KB Output is correct
112 Correct 2294 ms 342432 KB Output is correct
113 Correct 2204 ms 293120 KB Output is correct
114 Correct 2150 ms 292956 KB Output is correct
115 Correct 2179 ms 293084 KB Output is correct
116 Correct 2217 ms 292384 KB Output is correct
117 Correct 1865 ms 208600 KB Output is correct
118 Correct 1903 ms 208568 KB Output is correct
119 Correct 1887 ms 208572 KB Output is correct
120 Correct 1897 ms 208584 KB Output is correct
121 Correct 1858 ms 208584 KB Output is correct
122 Correct 1913 ms 208568 KB Output is correct
123 Correct 1901 ms 208512 KB Output is correct
124 Correct 1870 ms 208568 KB Output is correct
125 Correct 1847 ms 208452 KB Output is correct
126 Correct 1867 ms 208568 KB Output is correct