oj.uz

Submission #949841

# Submission time Handle Problem Language Result Execution time Memory
949841 2024-03-19T18:37:08 Z esomer Towers (NOI22_towers) C++17
11 / 100
 827 ms 177108 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int maxX = 1e6;
 
vector<int> cols[maxX + 1], rows[maxX + 1];
vector<bool> chosen[maxX + 1];
pair<int, int> ind[maxX + 1];
 
bool choose(int X, int Y){
	int lo = 0;
	int hi = (int)cols[X].size() - 1;
	int bst = -1;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		if(cols[X][mid] >= Y){
			bst = mid;
			hi = mid - 1;
		}else lo = mid + 1;
	}
	if(chosen[X][bst]) return true;
	chosen[X][bst] = true;
	return false;
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int N; cin >> N;
	vector<pair<int, int>> A(N);
	for(int i = 0; i < N; i++){
		int X, Y; cin >> X >> Y;
		A[i] = {X, Y};
		cols[X].push_back(Y);
		rows[Y].push_back(X);
	}
	for(int i = 1; i <= maxX; i++){
		sort(rows[i].begin(), rows[i].end());
		sort(cols[i].begin(), cols[i].end());
		ind[i] = {0, (int)rows[i].size() - 1};
		chosen[i].assign((int)cols[i].size(), false);
	}
	for(int i = 1; i <= maxX; i++){
		if((int)rows[i].size() > 0){
			choose(rows[i][0], i);
			choose(rows[i].back(), i);
		}
	}
	for(int i = maxX; i >= 1; i--){
		int f = -1, s = -1;
		for(int j = 0; j < (int)cols[i].size(); j++){
			if(chosen[i][j]){
				if(f == -1) f = j;
				s = j;
			}
		}
		for(int j = f + 1; j < s; j++){
			if(chosen[i][j]){
				int row = cols[i][j];
				ind[row].second--;
				if(ind[row].second > 0) choose(rows[row][ind[row].second], row);
				chosen[i][j] = false;
			}
		}
	}
	for(int i = 1; i <= maxX; i++){
		int f = -1, s = -1;
		for(int j = 0; j < (int)cols[i].size(); j++){
			if(chosen[i][j]){
				if(f == -1) f = j;
				s = j;
			}
		}
		for(int j = f + 1; j < s; j++){
			if(chosen[i][j]){
				int row = cols[i][j];
				ind[row].first++;
				if(ind[row].first < ind[row].second) choose(rows[row][ind[row].first], row);
				chosen[i][j] = false;
			}
		}
	}
	for(int i = 0; i < N; i++){
		if(choose(A[i].first, A[i].second)) cout << 1;
		else cout << 0;
	}
	cout << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 94300 KB Output is correct
2 Correct 34 ms 94124 KB Output is correct
3 Correct 31 ms 94296 KB Output is correct
4 Correct 31 ms 94296 KB Output is correct
5 Correct 30 ms 94300 KB Output is correct
6 Correct 31 ms 94544 KB Output is correct
7 Correct 30 ms 94332 KB Output is correct
8 Correct 31 ms 94300 KB Output is correct
9 Correct 31 ms 94300 KB Output is correct
10 Correct 36 ms 94300 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 94300 KB Output is correct
2 Correct 34 ms 94124 KB Output is correct
3 Correct 31 ms 94296 KB Output is correct
4 Correct 31 ms 94296 KB Output is correct
5 Correct 30 ms 94300 KB Output is correct
6 Correct 31 ms 94544 KB Output is correct
7 Correct 30 ms 94332 KB Output is correct
8 Correct 31 ms 94300 KB Output is correct
9 Correct 31 ms 94300 KB Output is correct
10 Correct 36 ms 94300 KB Output is correct
11 Correct 30 ms 94300 KB Output is correct
12 Correct 31 ms 94388 KB Output is correct
13 Correct 31 ms 94300 KB Output is correct
14 Correct 31 ms 94384 KB Output is correct
15 Correct 31 ms 94308 KB Output is correct
16 Correct 32 ms 94304 KB Output is correct
17 Correct 30 ms 94368 KB Output is correct
18 Correct 31 ms 94300 KB Output is correct
19 Incorrect 31 ms 94308 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 96896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 163416 KB Output is correct
2 Correct 435 ms 163436 KB Output is correct
3 Correct 454 ms 163460 KB Output is correct
4 Correct 425 ms 163408 KB Output is correct
5 Correct 438 ms 163320 KB Output is correct
6 Correct 799 ms 176912 KB Output is correct
7 Correct 816 ms 177108 KB Output is correct
8 Correct 792 ms 176792 KB Output is correct
9 Correct 827 ms 176720 KB Output is correct
10 Correct 797 ms 176724 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 94300 KB Output is correct
2 Correct 34 ms 94124 KB Output is correct
3 Correct 31 ms 94296 KB Output is correct
4 Correct 31 ms 94296 KB Output is correct
5 Correct 30 ms 94300 KB Output is correct
6 Correct 31 ms 94544 KB Output is correct
7 Correct 30 ms 94332 KB Output is correct
8 Correct 31 ms 94300 KB Output is correct
9 Correct 31 ms 94300 KB Output is correct
10 Correct 36 ms 94300 KB Output is correct
11 Correct 30 ms 94300 KB Output is correct
12 Correct 31 ms 94388 KB Output is correct
13 Correct 31 ms 94300 KB Output is correct
14 Correct 31 ms 94384 KB Output is correct
15 Correct 31 ms 94308 KB Output is correct
16 Correct 32 ms 94304 KB Output is correct
17 Correct 30 ms 94368 KB Output is correct
18 Correct 31 ms 94300 KB Output is correct
19 Incorrect 31 ms 94308 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 94300 KB Output is correct
2 Correct 34 ms 94124 KB Output is correct
3 Correct 31 ms 94296 KB Output is correct
4 Correct 31 ms 94296 KB Output is correct
5 Correct 30 ms 94300 KB Output is correct
6 Correct 31 ms 94544 KB Output is correct
7 Correct 30 ms 94332 KB Output is correct
8 Correct 31 ms 94300 KB Output is correct
9 Correct 31 ms 94300 KB Output is correct
10 Correct 36 ms 94300 KB Output is correct
11 Correct 30 ms 94300 KB Output is correct
12 Correct 31 ms 94388 KB Output is correct
13 Correct 31 ms 94300 KB Output is correct
14 Correct 31 ms 94384 KB Output is correct
15 Correct 31 ms 94308 KB Output is correct
16 Correct 32 ms 94304 KB Output is correct
17 Correct 30 ms 94368 KB Output is correct
18 Correct 31 ms 94300 KB Output is correct
19 Incorrect 31 ms 94308 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 94300 KB Output is correct
2 Correct 34 ms 94124 KB Output is correct
3 Correct 31 ms 94296 KB Output is correct
4 Correct 31 ms 94296 KB Output is correct
5 Correct 30 ms 94300 KB Output is correct
6 Correct 31 ms 94544 KB Output is correct
7 Correct 30 ms 94332 KB Output is correct
8 Correct 31 ms 94300 KB Output is correct
9 Correct 31 ms 94300 KB Output is correct
10 Correct 36 ms 94300 KB Output is correct
11 Correct 30 ms 94300 KB Output is correct
12 Correct 31 ms 94388 KB Output is correct
13 Correct 31 ms 94300 KB Output is correct
14 Correct 31 ms 94384 KB Output is correct
15 Correct 31 ms 94308 KB Output is correct
16 Correct 32 ms 94304 KB Output is correct
17 Correct 30 ms 94368 KB Output is correct
18 Correct 31 ms 94300 KB Output is correct
19 Incorrect 31 ms 94308 KB Output isn't correct
20 Halted 0 ms 0 KB -