Submission #1247530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247530		Tob	Zvijezda (COCI19_zvijezda)	C++20	110 / 110	79 ms	2120 KiB

zvijezda

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pii;
typedef pair <ld, ld> pdd;

const int N = 1e5 + 7;

int n, t;
pii co[N];

bool ccw(pdd x, pdd y, pdd z) {return x.F*(y.S-z.S)+y.F*(z.S-x.S)+z.F*(x.S-y.S)>0;}

bool check(int x, pii y) {
	return !ccw(co[(x+1)%n], co[x], y);
}

int get(int l, pii p, bool sid) {
	int lo = 0, hi = n/2;
	if (!sid) {
		while (lo < hi) {
			int mid = (lo+hi+1)/2;
			if (check(l+mid-1, p)) lo = mid;
			else hi = mid-1;
		}
		return lo;
	}
	while (lo < hi) {
		int mid = (lo+hi+1)/2;
		if (check(l+n/2-mid, p)) lo = mid;
		else hi = mid-1;
	}
	return lo;
}

int main () {
	FIO;
	cin >> t >> n;
	
	for (int i = 0; i < n; i++) cin >> co[i].F >> co[i].S;
	
	ll q, cnt = 0; cin >> q;
	while (q--) {
		ll a, b; cin >> a >> b;
		a ^= t*cnt*cnt*cnt; b ^= t*cnt*cnt*cnt;
		pii p = {a, b};
		int o = check(0, p), o2 = check(n/2, p);
		int res = 0;
		if (o == o2) {
			if (o) res = 1;
		}
		else {
			int sum = 0;
			if (o) sum += get(0, p, 0);
			else sum += get(0, p, 1);
			if (o2) sum += get(n/2, p, 0);
			else sum += get(n/2, p, 1);
			res = (sum > n/2);
		}
		cout << (res ? "DA\n" : "NE\n");
		cnt += res;
	}

	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60