CSES - Datatähti Open 2019

CSES - Datatähti Open 2019 - Results

Submission details
Task:	Function
Sender:	zscoder
Submission time:	2019-01-18 11:11:51 +0200
Language:	C++
Status:	READY
Result:	45

Feedback
group	verdict	score
#1	ACCEPTED	45
#2	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1	details
#2	ACCEPTED	0.02 s	1	details
#3	ACCEPTED	0.01 s	1	details
#4	ACCEPTED	0.03 s	1	details
#5	ACCEPTED	0.13 s	1	details
#6	ACCEPTED	0.03 s	1	details
#7	ACCEPTED	0.04 s	1	details
#8	ACCEPTED	0.05 s	1	details
#9	ACCEPTED	0.03 s	1	details
#10	WRONG ANSWER	0.02 s	2	details
#11	ACCEPTED	0.03 s	2	details
#12	ACCEPTED	0.03 s	2	details
#13	ACCEPTED	0.02 s	2	details
#14	ACCEPTED	0.15 s	2	details
#15	ACCEPTED	0.14 s	2	details
#16	ACCEPTED	0.12 s	2	details
#17	ACCEPTED	0.14 s	2	details
#18	ACCEPTED	0.09 s	2	details
#19	ACCEPTED	0.09 s	2	details
#20	ACCEPTED	0.09 s	2	details
#21	WRONG ANSWER	0.03 s	2	details
#22	TIME LIMIT EXCEEDED	--	2	details
#23	TIME LIMIT EXCEEDED	--	2	details
#24	TIME LIMIT EXCEEDED	--	2	details
#25	TIME LIMIT EXCEEDED	--	2	details
#26	TIME LIMIT EXCEEDED	--	2	details
#27	TIME LIMIT EXCEEDED	--	2	details
#28	ACCEPTED	0.73 s	2	details
#29	ACCEPTED	0.98 s	2	details
#30	ACCEPTED	0.03 s	2	details
#31	ACCEPTED	0.01 s	2	details
#32	ACCEPTED	0.01 s	2	details
#33	ACCEPTED	0.02 s	2	details
#34	ACCEPTED	0.14 s	2	details
#35	TIME LIMIT EXCEEDED	--	2	details

Compiler report

input/code.cpp: In function 'std::vector<std::pair<long double, long double> > intersect(std::vector<std::pair<long double, long double> >, std::vector<std::pair<long double, long double> >)':
input/code.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b.size();i++)
              ~^~~~~~~~~
input/code.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++)
              ~^~~~~~~~~
input/code.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<b.size();j++)
               ~^~~~~~~~~
input/code.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<nw.size();i++)
              ~^~~~~~~~~~

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef pair<ld,ld> interval;
 
interval cross(interval a, interval b)
{
	interval nw = mp(max(a.fi,b.fi),min(a.se,b.se));
	if(nw.fi>nw.se) return mp(-1,-1);
	else return nw;
}
 
vector<interval> intersect(vector<interval> a, vector<interval> b)
{
	vector<interval> b2;
	for(int i=0;i<b.size();i++)
	{
		if(b[i].fi>b[i].se) continue;
		b2.pb(b[i]);
	}
	b=b2;
	vector<interval> nw;
	for(int i=0;i<a.size();i++)
	{
		for(int j=0;j<b.size();j++)
		{
			interval x = cross(a[i],b[j]);
			if(x.fi<0) continue;
			nw.pb(x);
		}
	}
	if(nw.empty()) return {};
	sort(nw.begin(),nw.end());
	ld l=nw[0].fi; ld r=nw[0].se;
	vector<interval> res;
	for(int i=1;i<nw.size();i++)
	{
		ld L = nw[i].fi;
		ld R = nw[i].se;
		if(L>r)
		{
			res.pb(mp(l,r));
			l=L; r=R;
		}
		else
		{
			r=max(r,R);
		}
	}
	res.pb(mp(l,r));
	return res;
}
const ld eps=ld(1e-9);
ld PI=acos(-1);
void solve()
{
	int n; cin>>n;
	vector<ii> vec; 
	for(int i=0;i<n;i++)
	{
		int x,y; cin>>x>>y;
		vec.pb(mp(x,y));
	}
	for(int sign=0;sign<2;sign++)
	{
		vector<interval> V;
		V.pb({0,PI*0.5-eps});
		for(int i=1;i<n;i++)
		{
			ll dx = vec[i-1].fi-vec[i].fi;
			ll dy = vec[i-1].se-vec[i].se;
			vector<interval> nw;
			//check 0,pi/2
			if(!sign)
			{
				if(dx<0) nw.pb({0,0});
			}
			else
			{
				if(dx>0) nw.pb({0,0});
			}
			if(dy==0) 
			{
				if(dx!=0)
				{
					if((dx<0)^(!sign)) 
					{
						nw.pb({0,PI*0.5-eps});
					}
				}
			}
			if(dx==0)
			{
				if(dy!=0)
				{
					if((dy>0)^(!sign))
					{
						nw.pb({eps,PI*0.5-eps});
					}
				}
			}
			//cerr<<"NW : "<<nw.size()<<'\n';
			if(dx!=0&&dy!=0)
			{
				ld ratio = ld(dx)/ld(dy);
				int s = sign;
				if(dy<0) s^=1;
				//0,PI/2
				//tan(a)>ratio
				{
					ld tmp = atan(ratio);
					tmp=max(tmp,ld(0));
					//cerr<<s<<' '<<tmp<<'\n';
					if(s) nw.pb({tmp+eps,PI*0.5-eps});
					else nw.pb({eps,tmp-eps});
				}
			}
			/*
			for(interval x:nw)
			{
				cerr<<fixed<<setprecision(10)<<x.fi<<' '<<x.se<<'\n';
			}
			cerr<<'\n';
			*/
			vector<interval> N = intersect(V,nw);
			V=N;
			/*
			for(interval x:N)
			{
				cerr<<fixed<<setprecision(10)<<x.fi<<' '<<x.se<<'\n';
			}
			cerr<<"END"<<'\n';
			*/
		}
		if(!V.empty()) {cout<<"YES\n"; return ;}
		//cerr<<"LOOP "<<sign<<" COMPLETE\n";
	}
	for(int sign=0;sign<2;sign++)
	{
		vector<interval> V;
		V.pb({0,PI*0.5-eps});
		for(int i=1;i<n;i++)
		{
			ll dx = vec[i-1].fi-vec[i].fi;
			ll dy = vec[i].se-vec[i-1].se;
			vector<interval> nw;
			//check 0,pi/2
			if(!sign)
			{
				if(dy>0) nw.pb({0,0});
			}
			else
			{
				if(dy<0) nw.pb({0,0});
			}
			if(dy==0) 
			{
				if(dx!=0)
				{
					if((dx<0)^(!sign)) 
					{
						nw.pb({0,PI*0.5-eps});
					}
				}
			}
			if(dx==0)
			{
				if(dy!=0)
				{
					if((dy>0)^(!sign))
					{
						nw.pb({eps,PI*0.5-eps});
					}
				}
			}
			//cerr<<"NW : "<<nw.size()<<'\n';
			if(dx!=0&&dy!=0)
			{
				ld ratio = ld(dy)/ld(dx);
				int s = sign;
				if(dx<0) s^=1;
				//0,PI/2
				//tan(a)>ratio
				{
					ld tmp = atan(ratio);
					tmp=max(tmp,ld(0));
					if(!s) nw.pb({tmp+eps,PI*0.5-eps});
					else nw.pb({eps,tmp-eps});
				}
			}
			vector<interval> N = intersect(V,nw);
			V=N;
			/*
			for(interval x:N)
			{
				cerr<<fixed<<setprecision(10)<<x.fi<<' '<<x.se<<'\n';
			}
			cerr<<"END"<<'\n';
			*/
		}
		if(!V.empty()) {cout<<"YES\n"; return ;}
	}
	cout<<"NO\n";
}
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin>>t;
	while(t--) solve();
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
`12 2 0 0 1 1 5 ...` view save

correct output
`YES YES NO YES YES ...` view save

user output
`YES YES NO YES YES ...` view save

Test 2

Group: 1

Verdict: ACCEPTED

input
`100 2 92 30 22 44 2 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` Truncated

Test 3

Group: 1

Verdict: ACCEPTED

input
`100 3 -55 -98 -59 -55 -2 88 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` Truncated

Test 4

Group: 1

Verdict: ACCEPTED

input
`100 4 87 81 -84 42 18 -46 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` Truncated

Test 5

Group: 1

Verdict: ACCEPTED

input
`100 1000 -81 38 92 -21 -10 -65 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` Truncated

Test 6

Group: 1

Verdict: ACCEPTED

input
`100 110 -99 -9 -98 -9 -96 -8 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` Truncated

Test 7

Group: 1

Verdict: ACCEPTED

input
`100 78 -100 95 -99 96 -98 95 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` Truncated

Test 8

Group: 1

Verdict: ACCEPTED

input
`100 201 -100 97 -100 96 -99 99 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` Truncated

Test 9

Group: 1

Verdict: ACCEPTED

input
`100 45 -100 89 -100 90 -97 90 ...` view save

correct output
`YES NO NO NO NO ...` view save

user output
`YES NO NO NO NO ...` Truncated

Test 10

Group: 2

Verdict: WRONG ANSWER

input
`13 2 0 0 1 1 5 ...` view save

correct output
`YES YES NO YES YES ...` view save

user output
`YES YES NO YES NO ...` view save

Test 11

Group: 2

Verdict: ACCEPTED

input
`100 2 -517113909 -39540276 -209411537 -831819487 2 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` Truncated

Test 12

Group: 2

Verdict: ACCEPTED

input
`100 3 -991349544 139282777 646238126 16140762 -4488261 817588303 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` Truncated

Test 13

Group: 2

Verdict: ACCEPTED

input
`100 4 891187584 -889373775 -453505448 -469134344 -683807769 8725517 ...` view save

correct output
`YES NO YES NO NO ...` view save

user output
`YES NO YES NO NO ...` Truncated

Test 14

Group: 2

Verdict: ACCEPTED

input
`100 1000 -866614983 -994037153 775605588 -328510132 390868551 927606059 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` Truncated

Test 15

Group: 2

Verdict: ACCEPTED

input
`100 1000 -911073332 -1000000000 -905159999 -1000000000 -904949593 -999999999 ...` view save

correct output
`YES YES YES NO NO ...` view save

user output
`YES YES YES NO NO ...` Truncated

Test 16

Group: 2

Verdict: ACCEPTED

input
`100 1000 -1000000000 950042028 -946551105 -1000000000 -940508390 -1000000000 ...` view save

correct output
`NO YES YES YES NO ...` view save

user output
`NO YES YES YES NO ...` Truncated

Test 17

Group: 2

Verdict: ACCEPTED

input
`100 1000 -949977239 -1000000000 -948279892 -1000000000 -947497811 -999999999 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` Truncated

Test 18

Group: 2

Verdict: ACCEPTED

input
`100 806 -899 -1000 -898 -1000 -896 -999 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` Truncated

Test 19

Group: 2

Verdict: ACCEPTED

input
`100 777 -1000 914 -1000 915 -999 916 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` Truncated

Test 20

Group: 2

Verdict: ACCEPTED

input
`100 775 -999 998 -995 -1000 -994 -1000 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` Truncated

Test 21

Group: 2

Verdict: WRONG ANSWER

input
`13 2 0 0 1 1 5 ...` view save

correct output
`YES YES NO YES YES ...` view save

user output
`YES YES NO YES NO ...` view save

Test 22

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`1 999748 -995394098 -1000000000 -995392159 -1000000000 -995386584 -999999999 ...` view save

correct output
`NO` view save

user output
(empty)

Test 23

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`1 1000000 -954368893 -1000000000 -954366895 -1000000000 -954364896 -999999999 ...` view save

correct output
`YES` view save

user output
(empty)

Test 24

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`1 1000000 -1000000000 928772368 -1000000000 928772506 -999999999 928772642 ...` view save

correct output
`YES` view save

user output
(empty)

Test 25

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`1 999754 -901705699 -1000000000 -901702695 -1000000000 -901702062 -999999999 ...` view save

correct output
`NO` view save

user output
(empty)

Test 26

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`100 10000 -1000000000 919783772 -918885599 -1000000000 -918825263 -1000000000 ...` view save

correct output
`NO YES YES NO NO ...` view save

user output
(empty)

Test 27

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`10 99998 -997024120 -77018772 -997011201 -77017738 -996986132 -77015834 ...` view save

correct output
`YES YES NO YES YES ...` view save

user output
(empty)

Test 28

Group: 2

Verdict: ACCEPTED

input
`100 7934 -10000 9905 -10000 9906 -9999 9906 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` Truncated

Test 29

Group: 2

Verdict: ACCEPTED

input
`100 9710 -99754 -6983 -99786 -6055 -99751 -6548 ...` view save

correct output
`YES NO NO NO NO ...` view save

user output
`YES NO NO NO NO ...` Truncated

Test 30

Group: 2

Verdict: ACCEPTED

input
`100 2 802396401 -641287652 30956766 -527704723 2 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` Truncated

Test 31

Group: 2

Verdict: ACCEPTED

input
`100 3 755025461 -953536159 -402145543 137775005 -700733185 821755784 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` Truncated

Test 32

Group: 2

Verdict: ACCEPTED

input
`100 4 -673213071 571383249 -963633735 -859013318 -591788323 791136643 ...` view save

correct output
`NO NO NO NO YES ...` view save

user output
`NO NO NO NO YES ...` Truncated

Test 33

Group: 2

Verdict: ACCEPTED

input
`100 5 -124483012 623794901 233757283 -234519096 -987338502 737259422 ...` view save

correct output
`NO NO YES NO NO ...` view save

user output
`NO NO YES NO NO ...` Truncated

Test 34

Group: 2

Verdict: ACCEPTED

input
`100 1000 154383911 872030445 -9594726 190227899 908758769 -9615631 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` Truncated

Test 35

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`100 10000 642800667 -694556052 -343795089 -341227394 800920828 676674460 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
(empty)

Datatähti Open 2019

Function

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Tasks

Submissions (zscoder)