Submission #205728

#	Time	Username	Problem	Language	Result	Execution time	Memory
205728		mraron	Zvijezda (COCI19_zvijezda)	C++14	110 / 110	683 ms	8184 KiB

zvijezda

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
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;*/
	if(ld(b.yy)*ld(c.xx)>ld(c.yy)*ld(b.xx)) return -1;
	else if(ld(b.yy)*ld(c.xx)<ld(c.yy)*ld(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 {
			auto binker=[&](pair<pt,pt> sd, int v, int l, int r, int pos) {
				int L=pos;
				for(int j=18;j>=0;j--) {
					int akt=L-(1<<j);
					if(akt>=l) {
						if(val(side(akt),Q)==v) L=akt;
					}
				}
				int R=pos;
				for(int j=18;j>=0;j--) {
					int akt=R+(1<<j);
					if(akt<=r) {
						if(val(side(akt),Q)==v) R=akt;
					}
				}
				//cerr<<l<<" "<<L<<" "<<R<<" "<<r<<"cucc\n";
				return R-L+1;
			};
			int egyik=binker(r1, val(r1,Q), 0, n/2-1,0);
			int masik=binker(r2, val(r2,Q), n/2, n-1,n/2);
			int sum=0;
			if(val(r1,Q)==1) sum+=egyik; else sum+=n/2-egyik;
			if(val(r2,Q)==1) sum+=masik; else sum+=n/2-masik;
			//cerr<<egyik<<" "<<masik<<" "<<sum<<"\n";
			if(sum>n/2) {
				cout<<"DA\n";
				x++;
			}
			else cout<<"NE\n";
			
		}
		
	}	
	
}

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