oj.uz

Submission #59762

# Submission time Handle Problem Language Result Execution time Memory
59762 2018-07-23T05:13:52 Z tmwilliamlin168 The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 178 ms 1400 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define fi first
#define se second

inline int in() {
	int result = 0;
	char ch = getchar_unlocked();
	while(true) {
		if(ch >= '0' && ch <= '9')
			break;
		ch = getchar_unlocked();
	}
	result = ch-'0';
	while(true) {
		ch = getchar_unlocked();
		if (ch < '0' || ch > '9')
			break;
		result = result*10 + (ch - '0');
	}
	return result;
}
inline void out(int x) {
	int rev=x, c=0;
	if(!x) {
		putchar_unlocked('0');
		return;
	}
	while(!(rev%10)) {
		++c;
		rev/=10;
	}
	rev=0;
	while(x) {
		rev=rev*10+x%10;
		x/=10;
	}
	while(rev) {
		putchar_unlocked(rev%10+'0');
		rev/=10;
	}
	while(c--)
		putchar_unlocked('0');
}
 
const int mxC=1e4, mxN=2e3;
int c, n, m;
ll w, h, sx, sy, cx[mxC], cy[mxC], tx[mxN], ty[mxN];
bool a1[mxC];
 
inline bool fc(pll a, pll b) {
	return a.fi*b.se<b.fi*a.se;
}
 
inline pll af(ll dx, ll dy) {
	return dy<0?pll(dx-abs(dx)+dy, abs(dx)-dy):pll(abs(dx)-dx+dy, abs(dx)+dy);
}
 
int main() {
	w=in(), h=in(), sx=in(), sy=in(), c=in();
	for(int i=0; i<c; ++i) {
		cx[i]=in();
		cy[i]=in();
	}
	n=in();
	for(int i=0; i<n; ++i) {
		tx[i]=in();
		ty[i]=in();
	}
	memset(a1, 1, c);
	for(int i=0; i<n; ++i) {
		pll pa=af(sx-tx[i], sy-ty[i]), pb={-3, 1}, pc={3, 1};
		for(int j=0; j<n; ++j) {
			if(j==i)
				continue;
			pll pd=af(tx[i]-tx[j], ty[i]-ty[j]);
			if(fc(pa, pd)&&fc(pd, pc))
				pc=pd;
			else if(fc(pd, pa)&&fc(pb, pd))
				pb=pd;
		}
		if(pb==pll(-3, 1)||pc==pll(3, 1)) {
			if(pb.fi==-3) {
				for(int j=0; j<n; ++j) {
					if(j==i)
						continue;
					pll pd=af(tx[i]-tx[j], ty[i]-ty[j]);
					if(fc(pb, pd))
						pb=pd;
				}
			} else {
				for(int j=0; j<n; ++j) {
					if(j==i)
						continue;
					pll pd=af(tx[i]-tx[j], ty[i]-ty[j]);
					if(fc(pd, pc))
						pc=pd;
				}
			}
			for(int j=0; j<c; ++j) {
				if(!a1[j])
					continue;
				pll pd=af(cx[j]-tx[i], cy[j]-ty[i]);
				a1[j]=fc(pb, pd)||fc(pd, pc);
			}
		} else {
			for(int j=0; j<c; ++j) {
				if(!a1[j])
					continue;
				pll pd=af(cx[j]-tx[i], cy[j]-ty[i]);
				a1[j]=fc(pb, pd)&&fc(pd, pc);
			}
		}
	}
	for(int i=0; i<c; ++i)
		m+=a1[i];
	out(m);
	putchar_unlocked('\n');
	for(int i=0; i<c; ++i) {
		if(a1[i]) {
			out(i+1);
			putchar_unlocked(' ');
		}
	}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 4 ms 440 KB Output is correct
4 Correct 3 ms 444 KB Output is correct
5 Correct 2 ms 524 KB Output is correct
6 Correct 2 ms 528 KB Output is correct
7 Correct 3 ms 532 KB Output is correct
8 Correct 3 ms 536 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 540 KB Output is correct
2 Correct 3 ms 580 KB Output is correct
3 Correct 2 ms 584 KB Output is correct
4 Correct 3 ms 624 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 3 ms 660 KB Output is correct
7 Correct 2 ms 676 KB Output is correct
8 Correct 3 ms 680 KB Output is correct
9 Correct 3 ms 684 KB Output is correct
10 Correct 3 ms 688 KB Output is correct
11 Correct 3 ms 808 KB Output is correct
12 Correct 3 ms 808 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 808 KB Output is correct
2 Correct 4 ms 808 KB Output is correct
3 Correct 3 ms 808 KB Output is correct
4 Correct 12 ms 808 KB Output is correct
5 Correct 5 ms 808 KB Output is correct
6 Correct 78 ms 808 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 840 KB Output is correct
2 Correct 178 ms 1140 KB Output is correct
3 Correct 58 ms 1248 KB Output is correct
4 Correct 81 ms 1400 KB Output is correct