oj.uz

Submission #98045

# Submission time Handle Problem Language Result Execution time Memory
98045 2019-02-20T02:50:59 Z jasony123123 The Forest of Fangorn (CEOI14_fangorn) C++11
100 / 100
 1735 ms 1288 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <array>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else
#endif
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll INF = 1e14;
/***********************CEOI 2014 D1 Fangorn*****************************************/

ll ccw(pii a, pii b, pii c) {
	int dx1 = b.first - a.first;
	int dy1 = b.second - a.second;
	int dx2 = c.first - a.first;
	int dy2 = c.second - a.second;
	return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}

bool cmp(pii a, pii b) {
	bool flg1 = a < mp(0, 0);
	bool flg2 = b < mp(0, 0);
	if (flg1 != flg2) return flg1 < flg2;
	return ccw(mp(0, 0), a, b) > 0;
}

pii sub(pii a, pii b) {
	return{ a.first - b.first, a.second - b.second };
}

pii mypos;
v<pair<int, pii>> potDest;
int n;
pii obst[2000];

void input() {
	cin >> mypos.first >> mypos.second;
	cin >> mypos.first >> mypos.second;
	int c; cin >> c;
	potDest.resize(c);
	FOR(i, 0, c) {
		potDest[i].first = i + 1;
		cin >> potDest[i].second.first >> potDest[i].second.second;
	}
	cin >> n;
	FOR(i, 0, n)
		cin >> obst[i].first >> obst[i].second;
}

void getDividers(v<pii> &ans, int x) {
	ans.reserve(n - 1);
	FOR(i, 0, n) if (i != x)
		ans.push_back(sub(obst[x], obst[i]));
	sort(all(ans), cmp);
}

int getIndex(v<pii> &dividers, pii pnt) {
	if (cmp(dividers.back(), pnt))
		return 0;
	if (cmp(pnt, dividers.front()))
		return 0;
	int x =  lower_bound(all(dividers), pnt, cmp) - dividers.begin();
	return x;
}

int main() {
	io();
	input();
	FOR(i, 0, n) {
		v<pii> dividers;
		getDividers(dividers, i);
		
		v<pair<int, pii>> okDest;
		int target = getIndex(dividers, sub(mypos, obst[i]));
		for (auto d : potDest)
			if (getIndex(dividers, sub(d.second, obst[i])) == target)
				okDest.push_back(d);
		potDest = okDest;

	/*	cout << "after tree " << i << "\n";
		for (auto p : potDest)
			cout << p.first << ", " << p.second << "\n";*/

	}

	cout << potDest.size() << "\n";
	for (auto x : potDest)
		cout << x.first << " ";
	return 0;
}

void gey() {
	io();
	int nd; cin >> nd;
	v<pii> dividers(nd);
	FOR(i, 0, nd) cin >> dividers[i].first >> dividers[i].second;
	sort(all(dividers), cmp);
	for (auto p : dividers)
		cout << p.first << " " << p.second << "\n";

	int nc; cin >> nc;
	FOR(i, 0, nc) {
		pii c; cin >> c.first >> c.second;
		cout << getIndex(dividers, c) << "\n";
	}
}

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 118 ms 476 KB Output is correct
5 Correct 23 ms 376 KB Output is correct
6 Correct 516 ms 504 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 512 KB Output is correct
2 Correct 1735 ms 1020 KB Output is correct
3 Correct 479 ms 912 KB Output is correct
4 Correct 1268 ms 1288 KB Output is correct