oj.uz

Submission #388523

# Submission time Handle Problem Language Result Execution time Memory
388523 2021-04-11T21:44:29 Z LucaDantas The Forest of Fangorn (CEOI14_fangorn) C++17
100 / 100
 2959 ms 720 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 1e4+10;

mt19937 rng(random_device{}());

struct Pt
{
	int x, y;
	Pt(int a = 0, int b = 0) : x(a), y(b) {}
	long long operator%(const Pt& p) const { return 1ll * x * p.y - 1ll * y * p.x; }
	Pt operator-(Pt p) { return Pt(x-p.x, y-p.y); }
	bool operator==(Pt p) const { return x == p.x && y == p.y; }
};

bool half(Pt p) { return p.y < 0 || (p.y == 0 && p.x < 0); }

bool operator<(const Pt& a, const Pt& b) {
	if(half(a) != half(b)) return half(a) < half(b);
	return a%b > 0;
}

Pt trees[maxn], camps[maxn];

bool vivo[maxn];

vector<pair<Pt, int>> pts;

int main() {
	int W, H;
	scanf("%d %d", &W, &H);
	int sx, sy; scanf("%d %d", &sx, &sy);
	int c; scanf("%d", &c);
	for(int i = 0, x, y; i < c; i++)
		scanf("%d %d", &x, &y), camps[i] = Pt(x, y), vivo[i] = 1;
	int n; scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		int x, y; scanf("%d %d", &x, &y);
		trees[i] = Pt(x, y);
	}
	
	shuffle(trees, trees+n, rng);

	for(int i = 0; i < n; i++) {
		pts.clear();
		pts = {{Pt(sx, sy) - trees[i], 1}};
		
		for(int j = 0; j < n; j++)
			if(i != j) pts.push_back({trees[i] - trees[j], 0});

		for(int j = 0; j < c; j++)
			if(vivo[j]) vivo[j] = 0, pts.push_back({camps[j] - trees[i], 2+j});

		sort(pts.begin(), pts.end());

		int pos = -1, sz = (int)pts.size();
		for(int j = 0; j < sz; j++)
			if(pts[j].second == 1) { pos = j; break; }

		for(int j = (pos+1)%sz; pts[j].second; j = (j+1)%sz)
			vivo[pts[j].second-2] = 1;

		for(int j = (pos+sz-1)%sz; pts[j].second; j = (j+sz-1)%sz)
			vivo[pts[j].second-2] = 1;
	}

	vector<int> ans;
	for(int i = 0; i < c; i++)
		if(vivo[i]) ans.push_back(i+1);
	printf("%ld\n", ans.size());
	for(int x : ans)
		printf("%d\n", x);
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |  scanf("%d %d", &W, &H);
      |  ~~~~~^~~~~~~~~~~~~~~~~
fangorn.cpp:33:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  int sx, sy; scanf("%d %d", &sx, &sy);
      |              ~~~~~^~~~~~~~~~~~~~~~~~~
fangorn.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |  int c; scanf("%d", &c);
      |         ~~~~~^~~~~~~~~~
fangorn.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |   scanf("%d %d", &x, &y), camps[i] = Pt(x, y), vivo[i] = 1;
      |   ~~~~~^~~~~~~~~~~~~~~~~
fangorn.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  int n; scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
fangorn.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |   int x, y; scanf("%d %d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 120 ms 460 KB Output is correct
5 Correct 25 ms 460 KB Output is correct
6 Correct 513 ms 492 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 827 ms 532 KB Output is correct
2 Correct 2959 ms 716 KB Output is correct
3 Correct 546 ms 720 KB Output is correct
4 Correct 569 ms 716 KB Output is correct