oj.uz

Submission #496648

# Submission time Handle Problem Language Result Execution time Memory
496648 2021-12-21T18:15:19 Z inksamurai Zvijezda (COCI19_zvijezda) C++17
20 / 110
 1000 ms 4552 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){
	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 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));
		// cout<<get(a[j],a[(j-1+n)%n],p)<<"\n";
		return pok;
	};

	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);
		// cout<<x<<" "<<y<<"\n";
		bool pok=0;
		rep(i,n/2){
			if(affine(i,pll{x,y})){
				pok=1;
				break;
			}
		}
		cout<<(pok?"DA\n":"NE\n");
		ans+=pok;
	}
//	
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 324 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 16 ms 336 KB Output is correct
6 Correct 17 ms 432 KB Output is correct
7 Correct 19 ms 464 KB Output is correct
8 Correct 27 ms 464 KB Output is correct
9 Correct 23 ms 336 KB Output is correct
10 Correct 27 ms 456 KB Output is correct
11 Correct 26 ms 460 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 324 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 16 ms 336 KB Output is correct
6 Correct 17 ms 432 KB Output is correct
7 Correct 19 ms 464 KB Output is correct
8 Correct 27 ms 464 KB Output is correct
9 Correct 23 ms 336 KB Output is correct
10 Correct 27 ms 456 KB Output is correct
11 Correct 26 ms 460 KB Output is correct
12 Correct 121 ms 4404 KB Output is correct
13 Correct 875 ms 4552 KB Output is correct
14 Execution timed out 1076 ms 1548 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 3948 KB Time limit exceeded
2 Halted 0 ms 0 KB -