oj.uz

Submission #985836

# Submission time Handle Problem Language Result Execution time Memory
985836 2024-05-19T04:32:45 Z duckindog Building Skyscrapers (CEOI19_skyscrapers) C++17
8 / 100
 44 ms 6756 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 150'000 + 10,
					dx[8] = {-1, -1, 0, 1, 1, -1, 0, 1},
					dy[8] = {-1, 0, -1, -1, 0, 1, 1, 1};
int n, type;

struct Point { 
	int r, c, idx;
	bool operator > (const auto& rhs) { 
		return make_pair(r, c) > make_pair(rhs.r, rhs.c); 
	}
	friend ostream& operator << (ostream& os, const auto& rhs) { 
		return os << rhs.r << " " << rhs.c << " " << rhs.idx;
	}
} p[N];

unordered_map<int, unordered_map<int, int>> rvs;
bool mk[N];

int32_t main() { 
	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> type;
	for (int i = 1; i <= n; ++i) {
		int r, c; cin >> r >> c;
		p[i] = {r, c, i};	
		rvs[r][c] = i;
	}
	Point st = p[1];
	for (int i = 1; i <= n; ++i) if (st > p[i]) st = p[i];

	queue<Point> q;
	q.push(st);
	mk[st.idx] = true;

	vector<int> answer;
	while (q.size()) { 
		auto [r, c, idx] = q.front(); q.pop();
		answer.push_back(idx);
		for (int i = 0; i < 8; ++i) { 
			int nR = r + dx[i], nC = c + dy[i],
					nxt = rvs[nR][nC];
			if (!nxt || mk[nxt]) continue;
			mk[nxt] = true;
			q.push(p[nxt]);
		}
	} 
	
	if (answer.size() != n)	{ cout << "No\n"; return 0; };
	cout << "YES\n";
	for (const auto& x : answer) cout << x << "\n";
}

Compilation message

skyscrapers.cpp:12:25: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   12 |  bool operator > (const auto& rhs) {
      |                         ^~~~
skyscrapers.cpp:15:50: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   15 |  friend ostream& operator << (ostream& os, const auto& rhs) {
      |                                                  ^~~~
skyscrapers.cpp: In function 'int32_t main()':
skyscrapers.cpp:52:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |  if (answer.size() != n) { cout << "No\n"; return 0; };
      |      ~~~~~~~~~~~~~~^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ans=YES N=1
2 Correct 1 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Correct 0 ms 348 KB ans=YES N=5
5 Correct 0 ms 348 KB ans=YES N=9
6 Correct 1 ms 348 KB ans=YES N=5
7 Correct 0 ms 348 KB ans=NO N=9
8 Correct 0 ms 348 KB ans=NO N=10
9 Correct 0 ms 348 KB ans=YES N=10
10 Correct 1 ms 348 KB ans=YES N=10
11 Correct 0 ms 348 KB ans=YES N=10
12 Correct 0 ms 348 KB ans=YES N=9
13 Correct 1 ms 348 KB ans=YES N=9
14 Correct 0 ms 348 KB ans=YES N=8
15 Correct 1 ms 348 KB ans=YES N=8
16 Correct 1 ms 348 KB ans=NO N=2

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ans=YES N=1
2 Correct 1 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Correct 0 ms 348 KB ans=YES N=5
5 Correct 0 ms 348 KB ans=YES N=9
6 Correct 1 ms 348 KB ans=YES N=5
7 Correct 0 ms 348 KB ans=NO N=9
8 Correct 0 ms 348 KB ans=NO N=10
9 Correct 0 ms 348 KB ans=YES N=10
10 Correct 1 ms 348 KB ans=YES N=10
11 Correct 0 ms 348 KB ans=YES N=10
12 Correct 0 ms 348 KB ans=YES N=9
13 Correct 1 ms 348 KB ans=YES N=9
14 Correct 0 ms 348 KB ans=YES N=8
15 Correct 1 ms 348 KB ans=YES N=8
16 Correct 1 ms 348 KB ans=NO N=2
17 Correct 0 ms 348 KB ans=YES N=17
18 Correct 0 ms 348 KB ans=YES N=25
19 Correct 1 ms 348 KB ans=YES N=100
20 Correct 1 ms 348 KB ans=YES N=185
21 Correct 1 ms 348 KB ans=NO N=174
22 Correct 1 ms 348 KB ans=YES N=90
23 Correct 1 ms 344 KB ans=YES N=63
24 Correct 0 ms 348 KB ans=YES N=87
25 Correct 1 ms 348 KB ans=YES N=183
26 Correct 1 ms 348 KB ans=YES N=188
27 Correct 1 ms 504 KB ans=YES N=183
28 Correct 1 ms 348 KB ans=YES N=189
29 Correct 1 ms 348 KB ans=YES N=200
30 Correct 1 ms 348 KB ans=YES N=190
31 Correct 1 ms 348 KB ans=YES N=187
32 Correct 1 ms 344 KB ans=YES N=187
33 Correct 1 ms 348 KB ans=YES N=182
34 Correct 1 ms 348 KB ans=YES N=184
35 Correct 1 ms 348 KB ans=YES N=188
36 Correct 0 ms 348 KB ans=YES N=181
37 Correct 1 ms 348 KB ans=YES N=188
38 Correct 1 ms 348 KB ans=YES N=191
39 Incorrect 1 ms 348 KB Added cell 196 (16,2) not reachable from infinity
40 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ans=YES N=1
2 Correct 1 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Correct 0 ms 348 KB ans=YES N=5
5 Correct 0 ms 348 KB ans=YES N=9
6 Correct 1 ms 348 KB ans=YES N=5
7 Correct 0 ms 348 KB ans=NO N=9
8 Correct 0 ms 348 KB ans=NO N=10
9 Correct 0 ms 348 KB ans=YES N=10
10 Correct 1 ms 348 KB ans=YES N=10
11 Correct 0 ms 348 KB ans=YES N=10
12 Correct 0 ms 348 KB ans=YES N=9
13 Correct 1 ms 348 KB ans=YES N=9
14 Correct 0 ms 348 KB ans=YES N=8
15 Correct 1 ms 348 KB ans=YES N=8
16 Correct 1 ms 348 KB ans=NO N=2
17 Correct 0 ms 348 KB ans=YES N=17
18 Correct 0 ms 348 KB ans=YES N=25
19 Correct 1 ms 348 KB ans=YES N=100
20 Correct 1 ms 348 KB ans=YES N=185
21 Correct 1 ms 348 KB ans=NO N=174
22 Correct 1 ms 348 KB ans=YES N=90
23 Correct 1 ms 344 KB ans=YES N=63
24 Correct 0 ms 348 KB ans=YES N=87
25 Correct 1 ms 348 KB ans=YES N=183
26 Correct 1 ms 348 KB ans=YES N=188
27 Correct 1 ms 504 KB ans=YES N=183
28 Correct 1 ms 348 KB ans=YES N=189
29 Correct 1 ms 348 KB ans=YES N=200
30 Correct 1 ms 348 KB ans=YES N=190
31 Correct 1 ms 348 KB ans=YES N=187
32 Correct 1 ms 344 KB ans=YES N=187
33 Correct 1 ms 348 KB ans=YES N=182
34 Correct 1 ms 348 KB ans=YES N=184
35 Correct 1 ms 348 KB ans=YES N=188
36 Correct 0 ms 348 KB ans=YES N=181
37 Correct 1 ms 348 KB ans=YES N=188
38 Correct 1 ms 348 KB ans=YES N=191
39 Incorrect 1 ms 348 KB Added cell 196 (16,2) not reachable from infinity
40 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB ans=NO N=1934
2 Correct 1 ms 604 KB ans=NO N=1965
3 Incorrect 1 ms 604 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 1702)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ans=YES N=1
2 Correct 1 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Correct 0 ms 348 KB ans=YES N=5
5 Correct 0 ms 348 KB ans=YES N=9
6 Correct 1 ms 348 KB ans=YES N=5
7 Correct 0 ms 348 KB ans=NO N=9
8 Correct 0 ms 348 KB ans=NO N=10
9 Correct 0 ms 348 KB ans=YES N=10
10 Correct 1 ms 348 KB ans=YES N=10
11 Correct 0 ms 348 KB ans=YES N=10
12 Correct 0 ms 348 KB ans=YES N=9
13 Correct 1 ms 348 KB ans=YES N=9
14 Correct 0 ms 348 KB ans=YES N=8
15 Correct 1 ms 348 KB ans=YES N=8
16 Correct 1 ms 348 KB ans=NO N=2
17 Correct 0 ms 348 KB ans=YES N=17
18 Correct 0 ms 348 KB ans=YES N=25
19 Correct 1 ms 348 KB ans=YES N=100
20 Correct 1 ms 348 KB ans=YES N=185
21 Correct 1 ms 348 KB ans=NO N=174
22 Correct 1 ms 348 KB ans=YES N=90
23 Correct 1 ms 344 KB ans=YES N=63
24 Correct 0 ms 348 KB ans=YES N=87
25 Correct 1 ms 348 KB ans=YES N=183
26 Correct 1 ms 348 KB ans=YES N=188
27 Correct 1 ms 504 KB ans=YES N=183
28 Correct 1 ms 348 KB ans=YES N=189
29 Correct 1 ms 348 KB ans=YES N=200
30 Correct 1 ms 348 KB ans=YES N=190
31 Correct 1 ms 348 KB ans=YES N=187
32 Correct 1 ms 344 KB ans=YES N=187
33 Correct 1 ms 348 KB ans=YES N=182
34 Correct 1 ms 348 KB ans=YES N=184
35 Correct 1 ms 348 KB ans=YES N=188
36 Correct 0 ms 348 KB ans=YES N=181
37 Correct 1 ms 348 KB ans=YES N=188
38 Correct 1 ms 348 KB ans=YES N=191
39 Incorrect 1 ms 348 KB Added cell 196 (16,2) not reachable from infinity
40 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6756 KB ans=NO N=66151
2 Correct 20 ms 4676 KB ans=NO N=64333
3 Incorrect 38 ms 5708 KB Contestant's solution is not lexicographically largest at index 69316 (69235 vs 7320)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB ans=NO N=1934
2 Correct 1 ms 604 KB ans=NO N=1965
3 Incorrect 1 ms 604 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 1702)
4 Halted 0 ms 0 KB -