Submission #456200

#	Time	Username	Problem	Language	Result	Execution time	Memory
456200		grt	Zvijezda (COCI19_zvijezda)	C++17	110 / 110	125 ms	8008 KiB

zvijezda

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

struct Point {
	ll x, y;
};

const int nax = 1e5 + 10;
int t, n, q;
Point p[nax];

__int128 det(Point a, Point b, Point c) {
	return (__int128)(b.x - a.x) * (c.y - a.y) - (__int128)(c.x - a.x) * (b.y - a.y);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> t >> n;
	for(int i = 0; i < n; ++i) {
		cin >> p[i].x >> p[i].y;
	}
	int cnt = 0;
	cin >> q;
	while(q--) {
		ll a, b;
		cin >> a >> b;
		a ^= (ll)cnt * cnt * cnt * t;
		b ^= (ll)cnt * cnt * cnt * t;
		bool sign = det(p[0], p[1], {a, b}) >= 0;
		bool sign2 = det(p[n/2], p[n/2 + 1], {a, b}) >= 0;
		if(sign && sign2) {
			cnt++;
			cout << "DA\n";
			continue;
		}
		int r = 0;
		int low = 0, high = n/2, mid;
		while(low <= high) {
			mid = (low + high) / 2;
			if((det(p[mid], p[(mid + 1) % n], {a, b}) >= 0) == sign) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}
		r = low - 1;
		low = n/2; high = n - 1;
		while(low <= high) {
			mid = (low + high) / 2;
			if((det(p[mid], p[(mid + 1) % n], {a, b}) >= 0) != sign) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}
		int l = low;
		//for(int i = n - 1; i >= 1; --i) {
			//if((det(p[i], p[(i + 1) % n], {a, b}) >= 0) == sign) {
				//l = i;
			//} else {
				//break;
			//}
		//}
		bool w = false;
		if(r == n - 1) {
			if(sign) w = true;
		} else {
			if(sign) {
				if(((n - l) % n) + r + 1 > n / 2) w = true;
			} else {
				if(((n - l) % n) + r + 1 < n / 2) w = true;
			}
		}
		cnt += w;
		if(w) cout << "DA\n";
		else cout << "NE\n";
	}
}

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