oj.uz

Submission #258857

# Submission time Handle Problem Language Result Execution time Memory
258857 2020-08-06T15:58:51 Z amoo_safar Hamburg Steak (JOI20_hamburg) C++14
15 / 100
 653 ms 83048 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 = 2e5 + 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 * 8;
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[N];

void Main(){

	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]);
	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]);
	
	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);

	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]);
			la = min(mxx - 1, R[i]);
			if(fst <= la) seg.pb(pii(fst + ln[0], la + ln[0]));
		}
		// 2
		if(U[i] >= mxy){
			fst = max(mnx + 1, L[i]);
			la = min(mxx - 1, R[i]);
			if(fst <= la) seg.pb(pii(fst + ln[1], la + ln[1]));
		}
		// 3
		if(L[i] <= mnx){
			fst = max(mny + 1, D[i]);
			la = min(mxy - 1, U[i]);
			if(fst <= la) seg.pb(pii(fst + ln[2], la + ln[2]));
		}
		// 4
		if(R[i] >= mxx){
			fst = max(mny + 1, D[i]);
			la = min(mxy - 1, U[i]);
			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 57 ms 75640 KB Output is correct
2 Correct 57 ms 75640 KB Output is correct
3 Correct 60 ms 75640 KB Output is correct
4 Correct 57 ms 75640 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 75564 KB Output is correct
2 Correct 58 ms 75640 KB Output is correct
3 Correct 57 ms 75640 KB Output is correct
4 Correct 61 ms 75644 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 75608 KB Output is correct
2 Correct 59 ms 75640 KB Output is correct
3 Correct 59 ms 75640 KB Output is correct
4 Correct 62 ms 75640 KB Output is correct
5 Correct 63 ms 75640 KB Output is correct
6 Correct 64 ms 75640 KB Output is correct
7 Correct 56 ms 75640 KB Output is correct
8 Correct 57 ms 75640 KB Output is correct
9 Correct 62 ms 75640 KB Output is correct
10 Correct 60 ms 75640 KB Output is correct
11 Correct 56 ms 75640 KB Output is correct
12 Correct 57 ms 75668 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 75640 KB Output is correct
2 Correct 56 ms 75664 KB Output is correct
3 Correct 59 ms 75640 KB Output is correct
4 Correct 62 ms 75640 KB Output is correct
5 Correct 62 ms 75640 KB Output is correct
6 Correct 61 ms 75640 KB Output is correct
7 Correct 57 ms 75640 KB Output is correct
8 Correct 64 ms 75616 KB Output is correct
9 Correct 59 ms 75640 KB Output is correct
10 Correct 59 ms 75640 KB Output is correct
11 Correct 61 ms 75640 KB Output is correct
12 Correct 57 ms 75652 KB Output is correct
13 Correct 66 ms 75640 KB Output is correct
14 Incorrect 73 ms 83048 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 75640 KB Output is correct
2 Correct 57 ms 75640 KB Output is correct
3 Correct 60 ms 75640 KB Output is correct
4 Correct 57 ms 75640 KB Output is correct
5 Correct 432 ms 82808 KB Output is correct
6 Correct 442 ms 82720 KB Output is correct
7 Correct 437 ms 82720 KB Output is correct
8 Correct 438 ms 82824 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 75564 KB Output is correct
2 Correct 58 ms 75640 KB Output is correct
3 Correct 57 ms 75640 KB Output is correct
4 Correct 61 ms 75644 KB Output is correct
5 Correct 456 ms 82816 KB Output is correct
6 Correct 437 ms 82820 KB Output is correct
7 Correct 456 ms 82816 KB Output is correct
8 Correct 436 ms 82808 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 75608 KB Output is correct
2 Correct 59 ms 75640 KB Output is correct
3 Correct 59 ms 75640 KB Output is correct
4 Correct 62 ms 75640 KB Output is correct
5 Correct 63 ms 75640 KB Output is correct
6 Correct 64 ms 75640 KB Output is correct
7 Correct 56 ms 75640 KB Output is correct
8 Correct 57 ms 75640 KB Output is correct
9 Correct 62 ms 75640 KB Output is correct
10 Correct 60 ms 75640 KB Output is correct
11 Correct 56 ms 75640 KB Output is correct
12 Correct 57 ms 75668 KB Output is correct
13 Correct 444 ms 82808 KB Output is correct
14 Correct 437 ms 82788 KB Output is correct
15 Correct 448 ms 82968 KB Output is correct
16 Correct 453 ms 82808 KB Output is correct
17 Correct 429 ms 82948 KB Output is correct
18 Correct 431 ms 82776 KB Output is correct
19 Correct 429 ms 83032 KB Output is correct
20 Correct 458 ms 82808 KB Output is correct
21 Correct 653 ms 82804 KB Output is correct
22 Correct 554 ms 82792 KB Output is correct
23 Correct 605 ms 82828 KB Output is correct
24 Correct 560 ms 82804 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 75640 KB Output is correct
2 Correct 56 ms 75664 KB Output is correct
3 Correct 59 ms 75640 KB Output is correct
4 Correct 62 ms 75640 KB Output is correct
5 Correct 62 ms 75640 KB Output is correct
6 Correct 61 ms 75640 KB Output is correct
7 Correct 57 ms 75640 KB Output is correct
8 Correct 64 ms 75616 KB Output is correct
9 Correct 59 ms 75640 KB Output is correct
10 Correct 59 ms 75640 KB Output is correct
11 Correct 61 ms 75640 KB Output is correct
12 Correct 57 ms 75652 KB Output is correct
13 Correct 66 ms 75640 KB Output is correct
14 Incorrect 73 ms 83048 KB Output isn't correct
15 Halted 0 ms 0 KB -