oj.uz

Submission #388520

# Submission time Handle Problem Language Result Execution time Memory
388520 2021-04-11T21:25:07 Z LucaDantas The Forest of Fangorn (CEOI14_fangorn) C++17
100 / 100
 2968 ms 972 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); }
	void operator-=(Pt p) { 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];

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);
	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);
	}
	
	// Dou um shuffle pra n ficar com muita gente viva toda hora
	shuffle(trees, trees+n, rng);

	memset(vivo, 1, sizeof vivo);

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

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

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

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

		assert(pos != -1);

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

		for(int j = (pos+sz-1)%sz; pts[j].second.first; j = (j+sz-1)%sz)
			vivo[pts[j].second.second] = 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:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |  scanf("%d %d", &W, &H);
      |  ~~~~~^~~~~~~~~~~~~~~~~
fangorn.cpp:32:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |  int sx, sy; scanf("%d %d", &sx, &sy);
      |              ~~~~~^~~~~~~~~~~~~~~~~~~
fangorn.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  int c; scanf("%d", &c);
      |         ~~~~~^~~~~~~~~~
fangorn.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |   scanf("%d %d", &x, &y), camps[i] = Pt(x, y);
      |   ~~~~~^~~~~~~~~~~~~~~~~
fangorn.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |  int n; scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
fangorn.cpp:38:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |   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 1 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 5 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 125 ms 492 KB Output is correct
5 Correct 26 ms 460 KB Output is correct
6 Correct 508 ms 556 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 588 KB Output is correct
2 Correct 2968 ms 972 KB Output is correct
3 Correct 538 ms 972 KB Output is correct
4 Correct 575 ms 972 KB Output is correct