Submission #205712

#	Time	Username	Problem	Language	Result	Execution time	Memory
205712		mraron	Zvijezda (COCI19_zvijezda)	C++14	0 / 110	597 ms	7872 KiB

zvijezda

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pt;
#define xx first
#define yy second
int ccw(pt a, pt b, pt c) {
	b.xx-=a.xx;b.yy-=a.yy;
	c.xx-=a.xx;c.yy-=a.yy;
	
	if(b.yy*c.xx<c.yy*b.xx) return -1;
	else if(b.yy*c.xx>c.yy*b.xx) return 1;
	return 0;
}
int n;
pt pts[1000001];

pair<pt,pt> side(int x) {
	x%=n;
	x+=n;
	return make_pair(pts[x%n], pts[(x+1)%n]);
}

int val(pair<pt,pt> sd, pt q) {
	return ccw(sd.xx,sd.yy,q)!=1;
}

int main() {
	int t;
	cin>>t;
	cin>>n;
	for(int i=0;i<n;++i) cin>>pts[i].xx>>pts[i].yy;
	int q;
	cin>>q;
	ll x=0;
	while(q--) {
		//0,n-1
		//0,n/2-1
		pt Q;
		cin>>Q.xx>>Q.yy;

		Q.xx^=t*x*x*x;
		Q.yy^=t*x*x*x;
		auto r1=side(0), r2=side(n/2);
		/*cerr<<r1.xx.xx<<" "<<r1.xx.yy<<" | "<<r1.yy.xx<<" "<<r1.yy.yy<<"r1\n"; 
		cerr<<r2.xx.xx<<" "<<r2.xx.yy<<" | "<<r2.yy.xx<<" "<<r2.yy.yy<<"r2\n"; 
		cerr<<val(r1,Q)<<" "<<val(r2,Q)<<"\n";
		for(int i=0;i<=n-1;++i) cerr<<val(side(i),Q)<<" ";
		cerr<<"\n";*/
		if(val(r1,Q)==1 && val(r2,Q)==1) {
			cout<<"DA\n";
			x++;
		}
		else if(val(r1,Q)==0 && val(r2,Q)==0) cout<<"NE\n";
		else {
			int v=val(r1,Q);
			int L=0;
			for(int j=18;j>=0;j--) {
				int akt=L-(1<<j);
				if(akt>=(n/2)-n) {
					if(val(side(akt),Q)==v) L=akt;
				}
			}
			int R=0;
			for(int j=18;j>=0;j--) {
				int akt=R+(1<<j);
				if(akt<=(n/2)) {
					if(val(side(akt),Q)==v) R=akt;
				}
			}
			int len=R-L+1;
			if((v==1 && len>n/2) || (v==0 && len<=n/2-1)) {
				cout<<"DA\n";
				x++;
			}
			else cout<<"NE\n";
			
		}
		
	}	
	
}

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