oj.uz

Submission #131853

# Submission time Handle Problem Language Result Execution time Memory
131853 2019-07-17T19:52:32 Z bogdan10bos The Forest of Fangorn (CEOI14_fangorn) C++14
80 / 100
 2677 ms 32888 KB 
/// ASE sucks
/// (Trappere nu esti hard, da)
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef double mydouble;

const int CMAX = 10005;
const int NMAX = 2005;

int H, W, X, Y, C, N;
int cx[CMAX], cy[CMAX];
int px[NMAX], py[NMAX], part[NMAX];
vector<mydouble> drp[NMAX];

int findPart(int id, mydouble val)
{
	int ans = 0;
	int p = 0, u = (int)drp[id].size() - 1;
	while(p <= u)
	{
		int mij = p + (u - p) / 2;
		if(drp[id][mij] >= val)
		{
			ans = mij;
			u = mij - 1;
		}
		else
			p = mij + 1;
	}
	return ans;
}

int main()
{
	scanf("%d%d", &H, &W);
	scanf("%d%d", &X, &Y);
	scanf("%d", &C);
	for(int i = 1; i <= C; i++)
		scanf("%d%d", &cx[i], &cy[i]);
	scanf("%d", &N);
	for(int i = 1; i <= N; i++)
		scanf("%d%d", &px[i], &py[i]);
	for(int i = 1; i <= N; i++)
	{
		for(int j = 1; j <= N; j++)
			if(i != j)
				drp[i].push_back(atan2(px[i] - px[j], py[i] - py[j]));
		sort(drp[i].begin(), drp[i].end());
	}

	for(int i = 1; i <= N; i++)
		part[i] = findPart(i, atan2(X - px[i], Y - py[i]));

	vector<int> ord;
	for(int i = 1; i <= N; i++)	ord.push_back(i);
	mt19937 g(chrono::high_resolution_clock::now().time_since_epoch().count());
	shuffle(ord.begin(), ord.end(), g);

	while( (int)ord.size() > 1100 )	ord.pop_back();

	vector<int> sol;
	for(int i = 1; i <= C; i++)
	{
		bool ok = true;
		for(auto &id: ord)
		{
			int prt = findPart(id, atan2(cx[i] - px[id], cy[i] - py[id]));
			if(prt != part[id])
			{
				ok = false;
				break;
			}
		}
		if(ok)	sol.push_back(i);
	}

	sort(sol.begin(), sol.end());
	printf("%d\n", (int)sol.size());
	for(auto x: sol)	printf("%d ", x);
	return 0;
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &H, &W);
  ~~~~~^~~~~~~~~~~~~~~~
fangorn.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &X, &Y);
  ~~~~~^~~~~~~~~~~~~~~~
fangorn.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &C);
  ~~~~~^~~~~~~~~~
fangorn.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &cx[i], &cy[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
fangorn.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &px[i], &py[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 476 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 2 ms 316 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 5 ms 760 KB Output is correct
12 Correct 5 ms 760 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 126 ms 8460 KB Output is correct
5 Correct 25 ms 2296 KB Output is correct
6 Correct 455 ms 32556 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 32516 KB Output is correct
2 Incorrect 2677 ms 32888 KB Output isn't correct
3 Halted 0 ms 0 KB -