oj.uz

Submission #496693

# Submission time Handle Problem Language Result Execution time Memory
496693 2021-12-21T21:38:57 Z inksamurai Zvijezda (COCI19_zvijezda) C++17
110 / 110
 99 ms 7880 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _32bB6rn ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using pll=pair<long long,long long>;
using vi=vector<int>;
 
 
ld ccw(pll a,pll b,pll c){
	return (ld)a.fi * (b.se - c.se) +
			(ld)b.fi * (c.se - a.se) +
			(ld)c.fi * (a.se - b.se);
}
 
bool get(pll a,pll b,pll c){
	// ccw -> false
	return ccw(a,b,c)<0;
}
 
int main(){
_32bB6rn;
	ll _t;
	cin>>_t;
	int n;
	cin>>n;
	vec(pll) a(n);
	rep(i,n){
		cin>>a[i].fi>>a[i].se;
	}
	auto affine=[&](int i,pll p)->int{
		int j=(i+n/2+1+n)%n;
		bool pok=!get(a[i],a[(i+1)%n],p) and get(a[j],a[(j-1+n)%n],p);
		pok=pok or (get(a[(i+1)%n],a[i],p) and !get(a[(j-1+n)%n],a[j],p));
		return pok?2:!get(a[i],a[(i+1)%n],p)?1:3;
	};
	auto bs=[&](pll p)->bool{
		int l=0,r=n-1,c=-1;
		while(l<=r){
			int m=(l+r)>>1;
			int val=affine(m,p);
			if(val==2) return true;
			if(val==1){
				l=m+1;
			}else{
				r=m-1;
			}
		}
		return false;
	};
 
	int q;
	cin>>q;
	ll ans=0;
	rep(_,q){
		ll x,y;
		cin>>x>>y;
		x=x^(_t*ans*ans*ans);
		y=y^(_t*ans*ans*ans);
		bool pok=bs({x,y});
		cout<<(pok?"DA\n":"NE\n");
		ans+=pok;
	}
//	
	return 0;
}

Compilation message

zvijezda.cpp: In lambda function:
zvijezda.cpp:48:17: warning: unused variable 'c' [-Wunused-variable]
   48 |   int l=0,r=n-1,c=-1;
      |                 ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 50 ms 512 KB Output is correct
13 Correct 58 ms 592 KB Output is correct
14 Correct 77 ms 3796 KB Output is correct
15 Correct 74 ms 5084 KB Output is correct
16 Correct 93 ms 7496 KB Output is correct
17 Correct 99 ms 7624 KB Output is correct
18 Correct 63 ms 4416 KB Output is correct
19 Correct 67 ms 5264 KB Output is correct
20 Correct 77 ms 6204 KB Output is correct
21 Correct 85 ms 7348 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 5648 KB Output is correct
2 Correct 94 ms 7880 KB Output is correct
3 Correct 81 ms 5260 KB Output is correct
4 Correct 94 ms 7872 KB Output is correct
5 Correct 96 ms 7880 KB Output is correct
6 Correct 94 ms 7528 KB Output is correct
7 Correct 92 ms 7484 KB Output is correct
8 Correct 92 ms 7880 KB Output is correct
9 Correct 88 ms 7196 KB Output is correct