oj.uz

Submission #29683

# Submission time Handle Problem Language Result Execution time Memory
29683 2017-07-20T10:29:28 Z cdemirer The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 2643 ms 2304 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

int W, H;
int xg, yg;
int C, N;
vii camps;
vii trees;
vii xsort_tree;
vi ans;

bool deq(double a, double b) {
	double d = a>b?a-b:b-a;
	return d < 1e-18;
}

bool cmp(const pair<double, int> &a, const pair<double, int> &b) {
	if (deq(a.first, b.first)) return a.second < b.second;
	else return a.first < b.first;
}

vi getSeq(int a, int b) {
	vi ret;
	vector<pair<double, int> > rDif, lDif;
	vii::iterator it = lower_bound(xsort_tree.begin(), xsort_tree.end(), mp(a, -1));
	if (it != xsort_tree.end()) {
		// fill right part
		while (it != xsort_tree.end() && (*it).first == a) {
			if (trees[ (*it).second ].second > b) rDif.pb(mp(1e20, (*it).second));
			else rDif.pb(mp(-1e20, (*it).second));
			it++;
		}
		for (; it != xsort_tree.end(); it++) {
			double tx = trees[ (*it).second ].first;
			double ty = trees[ (*it).second ].second;
			double egim = (ty - b) / (tx - a);
			rDif.pb(mp(egim, (*it).second));
		}
		sort(rDif.begin(), rDif.end(), cmp);
		for (int i = 0; i < rDif.size(); i++) {
			ret.pb(rDif[i].second);
		}
	}
	it = lower_bound(xsort_tree.begin(), xsort_tree.end(), mp(a, -1));
	if (it != xsort_tree.begin()) {
		// fill left part
		it--;
		while (it != xsort_tree.begin()) {
			double tx = trees[ (*it).second ].first;
			double ty = trees[ (*it).second ].second;
			double egim = (ty - b) / (tx - a);
			lDif.pb(mp(egim, (*it).second));
			it--;
		}
		double tx = trees[ (*it).second ].first;
		double ty = trees[ (*it).second ].second;
		double egim = (ty - b) / (tx - a);
		lDif.pb(mp(egim, (*it).second));
		sort(lDif.begin(), lDif.end(), cmp);
		for (int i = 0; i < lDif.size(); i++) {
			ret.pb(lDif[i].second);
		}
	}
	return ret;
}

inline int next(int x) {
	return (x+1)%N;
}

bool cyclequal(const vi &a, const vi &b) {
	int x = a[0];
	int p2 = 0;
	while (b[p2] != x) p2 = next(p2);
	int cnt = N;
	int p1 = 0;
	while (cnt--) {
		if (a[p1] != b[p2]) return false;
		p1 = next(p1);
		p2 = next(p2);
	}
	return true;
}

int main(int argc, char **argv) {

	//freopen("input", "r", stdin);
	//freopen("output", "w", stdout);

	scanf("%d%d", &W, &H);
	scanf("%d%d", &xg, &yg);
	scanf("%d", &C);
	camps.resize(C);
	for (int i = 0; i < C; i++) {
		scanf("%d%d", &(camps[i].first), &(camps[i].second));
	}
	scanf("%d", &N);
	trees.resize(N);
	for (int i = 0; i < N; i++) {
		scanf("%d%d", &(trees[i].first), &(trees[i].second));
		xsort_tree.pb(mp(trees[i].first, i));
	}
	sort(xsort_tree.begin(), xsort_tree.end());
	vi oseq = getSeq(xg, yg);
	for (int i = 0; i < C; i++) {
		vi s = getSeq(camps[i].first, camps[i].second);
		if (cyclequal(oseq, s)) {
			ans.pb(i+1);
		}
	}
	printf("%d\n", (int)ans.size());
	for (int i = 0; i < ans.size(); i++) {
		printf("%d ", ans[i]);
	}
	if (ans.size()>0) puts("");

	return 0;
}

Compilation message

fangorn.cpp: In function 'vi getSeq(int, int)':
fangorn.cpp:49:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < rDif.size(); i++) {
                     ^
fangorn.cpp:69:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < lDif.size(); i++) {
                     ^
fangorn.cpp: In function 'int main(int, char**)':
fangorn.cpp:121:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++) {
                    ^
fangorn.cpp:99:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &W, &H);
                       ^
fangorn.cpp:100:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &xg, &yg);
                         ^
fangorn.cpp:101:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &C);
                 ^
fangorn.cpp:104:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &(camps[i].first), &(camps[i].second));
                                                       ^
fangorn.cpp:106:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
fangorn.cpp:109:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &(trees[i].first), &(trees[i].second));
                                                       ^

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2028 KB Output is correct
2 Correct 0 ms 2028 KB Output is correct
3 Correct 0 ms 2028 KB Output is correct
4 Correct 0 ms 2028 KB Output is correct
5 Correct 0 ms 2028 KB Output is correct
6 Correct 0 ms 2168 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 2160 KB Output is correct
2 Correct 2329 ms 2304 KB Output is correct
3 Correct 2643 ms 2176 KB Output is correct
4 Correct 2479 ms 2184 KB Output is correct