Submission #1274834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274834		vulestamenkovic	Zvijezda (COCI19_zvijezda)	C++20	0 / 110	82 ms	1996 KiB

zvijezda

#include<bits/stdc++.h>
#define int long long
#define MAXN (int)1e5+5
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int x[MAXN],y[MAXN];
bool query(vector<array<int,2>> s){
	int j=0;
	for(int i=0;i<3;i++){
		while(s[i][0]==x[j]&&s[i][1]==y[j]){
			i=0;
			j++;
		}
	}
	int o=(s[1][0]-s[0][0])*(s[2][1]-s[1][1])-(s[2][0]-s[1][0])*(s[1][1]-s[0][1]),
		o2=(s[1][0]-s[0][0])*(y[j]-s[1][1])-(x[j]-s[1][0])*(s[1][1]-s[0][1]);
	return (abs(o+o2)==(abs(o)+abs(o2)));
}
void solve() {
	int t,n,q;cin>>t>>n;
	cin>>x[0]>>y[0];
	for(int i=1;i<n;i++){
		cin>>x[i]>>y[i];
	}
	cin>>q;
	int z=0;
	while(q--){
		int a,b;cin>>a>>b;
		a^=(t*z*z*z);
		b^=(t*z*z*z);
		int o=query({{x[0],y[0]},{x[1],y[1]},{a,b}}),
			o2=query({{x[n/2],y[n/2]},{x[n/2+1],y[n/2+1]},{a,b}});
		if(o==o2){
			z+=o;
			cout<<(o?"DA\n":"NE\n");continue;
		}
		int l=2,r=n/2,ans=1;
		while(l<=r){
			int s=(l+r)/2;
			if(query({{x[s-1],y[s-1]},{x[s],y[s]},{a,b}})==o){
				//cout<<x[s-1]<<' '<<y[s-1]<<' '<<x[s]<<' '<<y[s]<<'\n';
				l=s+1;
				ans=s;
			}else{
				r=s-1;
			}
		}
		l=n/2+2,r=n;
		int ans2=n+1;
		while(l<=r){
			int s=(l+r)/2;
			if(query({{x[s-1],y[s-1]},{x[s%n],y[s%n]},{a,b}})==o){
				r=s-1;
				ans2=s;
			}else{
				l=s+1;
			}
		}
		r=ans+n+1-ans2;
		//cout<<o<<' '<<r<<'\n';
		if((o&&r>n/2)||(!o&&r<n/2)){z++;
			cout<<"DA\n";
		}else{
			cout<<"NE\n";
		}
	}
}
int32_t main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int32_t T=1;//cin>>T;
	while(T--) {
		solve();
	}
	return 0;
}

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