QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#813918#9880. Origami Warpucup-team3161#AC ✓139ms4180kbC++1416.9kb2024-12-14 13:38:202024-12-14 13:38:25

Judging History

你现在查看的是最新测评结果

  • [2024-12-14 13:38:25]
  • 评测
  • 测评结果:AC
  • 用时:139ms
  • 内存:4180kb
  • [2024-12-14 13:38:20]
  • 提交

answer

// test 
//https://qoj.ac/submission/293248
//https://qoj.ac/problem/4866
#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ";
	dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

pi readpi(int off=0){
	int a,b;cin>>a>>b;
	return pi(a+off,b+off);
}

template<class t>
void print_single(t x,int suc=1){
	cout<<x;
	if(suc==1)
		cout<<"\n";
	if(suc==2)
		cout<<" ";
}

template<class t,class u>
void print_single(const pair<t,u>&p,int suc=1){
	print_single(p.a,2);
	print_single(p.b,suc);
}

template<class T>
void print_single(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print_single(v[i],i==int(v.size())-1?suc:2);
}

template<class T>
void print_offset(const vector<T>&v,ll off,int suc=1){
	rep(i,v.size())
		print_single(v[i]+off,i==int(v.size())-1?suc:2);
}

template<class T,size_t N>
void print_single(const array<T,N>&v,int suc=1){
	rep(i,N)
		print_single(v[i],i==int(N)-1?suc:2);
}

template<class T>
void print(const T&t){
	print_single(t);
}

template<class T,class ...Args>
void print(const T&t,const Args&...args){
	print_single(t,2);
	print(args...);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

void YES(bool ex=true){
	cout<<"YES\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void NO(bool ex=true){
	cout<<"NO\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void Yes(bool ex=true){
	cout<<"Yes\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void No(bool ex=true){
	cout<<"No\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
//#define CAPITAL
/*
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<"\n";
	#else
	cout<<"Yes"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<"\n";
	#else
	cout<<"No"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}*/
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<"\n";
	#else
	cout<<"Possible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<"\n";
	#else
	cout<<"Impossible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int topbit(ull t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int botbit(ull a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
int popcount(ull t){
	return __builtin_popcountll(t);
}
int bitparity(ll t){
	return __builtin_parityll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
ll mask(int i){
	return (ll(1)<<i)-1;
}
ull umask(int i){
	return (ull(1)<<i)-1;
}
ll minp2(ll n){
	if(n<=1)return 1;
	else return ll(1)<<(topbit(n-1)+1);
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class t> void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll rand_int(ll l, ll r) { //[l, r]
	//#ifdef LOCAL
	static mt19937_64 gen;
	/*#else
	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
	#endif*/
	return uniform_int_distribution<ll>(l, r)(gen);
}

ll rand_int(ll k){ //[0,k)
	return rand_int(0,k-1);
}

template<class t>
void myshuffle(vc<t>&a){
	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}

template<class t,class u>
int lwb(const vc<t>&v,const u&a){
	return lower_bound(all(v),a)-v.bg;
}
template<class t,class u>
bool bis(const vc<t>&v,const u&a){
	return binary_search(all(v),a);
}

vvc<int> readGraph(int n,int m){
	vvc<int> g(n);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		//sc.read(a,b);
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	return g;
}

vvc<int> readTree(int n){
	return readGraph(n,n-1);
}

template<class t>
vc<t> presum(const vc<t>&a){
	vc<t> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
vc<ll> presum(const vi&a){
	vc<ll> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
//BIT で数列を管理するときに使う (CF850C)
template<class t>
vc<t> predif(vc<t> a){
	gnr(i,1,si(a))a[i]-=a[i-1];
	return a;
}
template<class t>
vvc<ll> imos(const vvc<t>&a){
	int n=si(a),m=si(a[0]);
	vvc<ll> b(n+1,vc<ll>(m+1));
	rep(i,n)rep(j,m)
		b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j];
	return b;
}

//verify してないや
void transvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void transvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[j][i]=a[i][j];
	}
	a.swap(b);
	transvvc(n,m,args...);
}
//CF854E
void rotvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void rotvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[m-1-j][i]=a[i][j];
	}
	a.swap(b);
	rotvvc(n,m,args...);
}

//ソートして i 番目が idx[i]
//CF850C
template<class t>
vi sortidx(const vc<t>&a){
	int n=si(a);
	vi idx(n);iota(all(idx),0);
	sort(all(idx),[&](int i,int j){return a[i]<a[j];});
	return idx;
}
//vs[i]=a[idx[i]]
//例えば sortidx で得た idx を使えば単にソート列になって返ってくる
//CF850C
template<class t>
vc<t> a_idx(const vc<t>&a,const vi&idx){
	int n=si(a);
	assert(si(idx)==n);
	vc<t> vs(n);
	rep(i,n)vs[i]=a[idx[i]];
	return vs;
}
//CF850C
vi invperm(const vi&p){
	int n=si(p);
	vi q(n);
	rep(i,n)q[p[i]]=i;
	return q;
}

template<class t,class s=t>
s SUM(const vc<t>&a){
	return accumulate(all(a),s(0));
}
template<class t,size_t K,class s=t>
s SUM(const array<t,K>&a){
	return accumulate(all(a),s(0));
}

template<class t>
t MAX(const vc<t>&a){
	return *max_element(all(a));
}

template<class t>
pair<t,int> MAXi(const vc<t>&a){
	auto itr=max_element(all(a));
	return mp(*itr,itr-a.bg);
}

template<class A>
auto MIN(const A&a){
	return *min_element(all(a));
}

template<class t>
pair<t,int> MINi(const vc<t>&a){
	auto itr=min_element(all(a));
	return mp(*itr,itr-a.bg);
}

vi vid(int n){
	vi res(n);iota(all(res),0);
	return res;
}

template<class S>
void soin(S&s){
	sort(all(s));
}

template<class S,class F>
void soin(S&s,F&&f){
	sort(all(s),forward<F>(f));
}

template<class S>
S soout(S s){
	soin(s);
	return s;
}

template<class S>
void rein(S&s){
	reverse(all(s));
}

template<class S>
S reout(S s){
	rein(s);
	return s;
}

template<class t,class u>
pair<t,u>&operator+=(pair<t,u>&a,pair<t,u> b){
	a.a+=b.a;a.b+=b.b;return a;}
template<class t,class u>
pair<t,u>&operator-=(pair<t,u>&a,pair<t,u> b){
	a.a-=b.a;a.b-=b.b;return a;}
template<class t,class u>
pair<t,u> operator+(pair<t,u> a,pair<t,u> b){return mp(a.a+b.a,a.b+b.b);}
template<class t,class u>
pair<t,u> operator-(pair<t,u> a,pair<t,u> b){return mp(a.a-b.a,a.b-b.b);}

template<class t>
t gpp(vc<t>&vs){
	assert(si(vs));
	t res=move(vs.back());
	vs.pop_back();
	return res;
}

template<class t,class u>
void pb(vc<t>&a,const vc<u>&b){
	a.insert(a.ed,all(b));
}

template<class t,class...Args>
vc<t> cat(vc<t> a,Args&&...b){
	(pb(a,forward<Args>(b)),...);
	return a;
}

template<class t,class u>
vc<t>& operator+=(vc<t>&a,u x){
	for(auto&v:a)v+=x;
	return a;
}

template<class t,class u>
vc<t> operator+(vc<t> a,u x){
	return a+=x;
}

template<class t>
vc<t> operator+(const vc<t>&a,const vc<t>&b){
	vc<t> c(max(si(a),si(b)));
	rep(i,si(a))c[i]+=a[i];
	rep(i,si(b))c[i]+=b[i];
	return c;
}

template<class t,class u>
vc<t>& operator-=(vc<t>&a,u x){
	for(auto&v:a)v-=x;
	return a;
}

template<class t,class u>
vc<t>& operator-(vc<t> a,u x){
	return a-=x;
}

template<class t,class u>
void remval(vc<t>&a,const u&v){
	a.erase(remove(all(a),v),a.ed);
}

template<class VS,class u>
void fila(VS&vs,const u&a){
	fill(all(vs),a);
}

template<class t,class u>
int findid(const vc<t>&vs,const u&a){
	auto itr=find(all(vs),a);
	if(itr==vs.ed)return -1;
	else return itr-vs.bg;
}

template<class t>
void rtt(vc<t>&vs,int i){
	rotate(vs.bg,vs.bg+i,vs.ed);
}


//デバッグ実行でオーバーフローするとコアダンプしがち

using int128=__int128_t;
using uint128=unsigned __int128_t;

istream& operator>>(istream&is,int128&res){
	res=0;
	string s;is>>s;
	int head=0;
	int128 w=1;
	if(s[0]=='-'){
		w=-1;
		head++;
	}
	while(head<int(s.size())){
		res=res*10+s[head++]-'0';
	}
	res*=w;
	return is;
}
ostream& operator<<(ostream&os,int128 i){
	if(i==0)
		return os<<0;
	static char buf[100];
	if(i<0){
		os<<"-";
		i=-i;
	}
	int p=0;
	while(i){
		buf[p++]='0'+i%10;
		i/=10;
	}
	reverse(buf,buf+p);
	buf[p]=0;
	return os<<buf;
}
ostream& operator<<(ostream&os,uint128 i){
	if(i==0)
		return os<<0;
	static char buf[100];
	int p=0;
	while(i){
		buf[p++]='0'+i%10;
		i/=10;
	}
	reverse(buf,buf+p);
	buf[p]=0;
	return os<<buf;
}
int128 abs(int128 a){
	return a<0?-a:a;
}
int botbit(int128 a){
	const int128 m=(int128(1)<<64)-1;
	if(a&m)return __builtin_ctzll(ll(a));
	else return __builtin_ctzll(ll(a>>64))+64;
}
int128 gcd(int128 a,int128 b){
	if(a<0)a=-a;
	if(b<0)b=-b;
	if(a==0)return b;
	if(b==0)return a;
	int128 s=botbit(a|b);
	a>>=botbit(a);
	do{
		b>>=botbit(b);
		if(a>b)swap(a,b);
		b-=a;
	}while(b);
	return a<<s;
}
const int128 inf128=int128(1)<<122;

int128 fdiv(int128 a,int128 b) { // floored division
	return a / b - ((a ^ b) < 0 && a % b); }
//a,c O(10^36)
//b,d O(10^18)
//a/b, c/d の大小比較
int cmpfrac(int128 a,int128 b,int128 c,int128 d){
	assert(b);
	assert(d);
	if(b<0){
		a=-a;
		b=-b;
	}
	if(d<0){
		c=-c;
		d=-d;
	}
	int128 x=fdiv(a,b),y=fdiv(c,d);
	if(x<y)return -1;
	if(x>y)return 1;
	int128 u=(a-x*b)*d,v=(c-y*d)*b;
	if(u<v)return -1;
	if(u>v)return 1;
	return 0;
}
bool inc(int128 a,int128 b,int128 c){
	return a<=b&&b<=c;
}

bool dbg=false;

using ld=long double;
using P=pair<int128,int128>;
using L=pair<P,P>;
struct Mirrors{
	vc<int128> vs;
	void add(int128 v){
		vs.pb(v);
	}
	int128 g;
	void init(){
		g=0;
		for(auto v:vs){
			g=gcd(g,v-vs[0]);
		}
	}
	void fund(int128&v){
		if(si(vs)){
			v-=vs[0];
			if(g==0){
				if(v<0)v=-v;
			}else{
				v%=(g*2);
				if(v<0)v+=g*2;
				if(v>g)v=g*2-v;
			}
			v+=vs[0];
		}
	}
};

void slv(){
	int n,q;cin>>n;
	vc<L> ls(n);
	rep(i,n){
		cin>>ls[i].a.a>>ls[i].a.b>>ls[i].b.a>>ls[i].b.b;
	}
	cin>>q;
	vc<L> qs(q);
	rep(i,q){
		cin>>qs[i].a.a>>qs[i].a.b>>qs[i].b.a>>qs[i].b.b;
	}
	
	P org=ls[0].a;
	P Xaxis=ls[0].b-ls[0].a;
	auto modify=[&](P&v){
		v-=org;
		int128 x=v.a*Xaxis.a+v.b*Xaxis.b;
		int128 y=v.a*(-Xaxis.b)+v.b*Xaxis.a;
		v.a=x;
		v.b=y;
	};
	rep(i,n){
		modify(ls[i].a);
		modify(ls[i].b);
	}
	rep(i,q){
		modify(qs[i].a);
		modify(qs[i].b);
	}
	//all 18
	
	bool irr=false;
	rep(i,n){
		P dir=ls[i].b-ls[i].a;
		if(dir.a&&dir.b&&abs(dir.a)!=abs(dir.b)){
			irr=true;
		}
	}
	
	vc<ld> ans(q,-1);
	if(irr){
		dmp("Irrational");
		vc<P> clist;//(36,18)
		bool dif=false;
		rep(i,n){
			auto [a,b]=ls[i];
			if(a.b!=b.b){
				int128 num=a.a*b.b-b.a*a.b;
				int128 den=b.b-a.b;
				clist.eb(num,den);
			}else if(a.b!=0){
				dif=true;
			}
		}
		assert(si(clist)>0);
		rep(i,si(clist)-1){
			auto [an,ad]=clist[i];
			auto [bn,bd]=clist[i+1];
			if(cmpfrac(an,ad,bn,bd)){
				dif=true;
			}
		}
		if(dif){
			dmp("Dif");
			rep(i,q){
				ans[i]=0;
			}
		}else{
			dmp("Center");
			ld c=ld(clist[0].a)/clist[0].b;
			auto dist=[&](P v){
				return sqrtl(sq(v.a-c)+sq(v.b));
			};
			rep(i,q){
				auto [a,b]=qs[i];
				ld ad=dist(a);
				ld bd=dist(b);
				ans[i]=abs(ad-bd);
			}
		}
	}else{
		dmp("Rational");
		bool has45=false;
		rep(i,n){
			P dir=ls[i].b-ls[i].a;
			if(dir.a&&dir.b){
				has45=true;
			}
		}
		if(has45){
			dmp("Has 45");
			
			{
				int128 c;
				rep(i,n){
					P dir=ls[i].b-ls[i].a;
					if(dir.a&&dir.b){
						dir.a/=dir.b;
						dir.b=1;
						int128 v=ls[i].a.a-ls[i].a.b*dir.a;
						c=v;
					}
				}
				rep(i,n){
					auto&[a,b]=ls[i];
					a.a-=c;
					b.a-=c;
				}
				rep(i,q){
					auto&[a,b]=qs[i];
					a.a-=c;
					b.a-=c;
				}
			}
			//0 is the center
			
			dmp(ls);
			
			rep(phase,2){
				Mirrors m;
				m.add(0);
				rep(i,n){
					P dir=ls[i].b-ls[i].a;
					if(dir.a&&dir.b){
						dir.a/=dir.b;
						dir.b=1;
						int128 v=ls[i].a.a-ls[i].a.b*dir.a;
						m.add(v);
					}else if(dir.a==0){
						m.add(ls[i].a.a);
					}else if(dir.b==0){
						m.add(ls[i].a.b);
					}else assert(false);
				}
				dmp(m.vs);
				m.init();
				assert(m.vs[0]==0);
				
				if(m.g==0){
					dmp("45 Centered");
				}else{
					dmp("45 Checkered");
				}
					
				auto work=[&](P&v){
					if(m.g==0){
						if(v.a<0)v.a*=-1;
						if(v.b<0)v.b*=-1;
						if(v.a<v.b)swap(v.a,v.b);
					}else{
						auto&[a,b]=v;
						m.fund(a);
						m.fund(b);
						
						dmp2(m.g,a,b);
						
						//if(!inc(0,a,m.g))exit(0);
						//if(!inc(0,b,m.g))exit(0);
						assert(inc(0,a,m.g));
						assert(inc(0,b,m.g));
						if(a+b>=m.g){
							tie(a,b)=mp(m.g-b,m.g-a);
						}
						if(a<b){
							swap(a,b);
						}
					}
				};
				
				const ld wei=phase==0?1:1/sqrtl(2);
				rep(i,q){
					auto [a,b]=qs[i];
					work(a);
					work(b);
					
					P dif=a-b;
					chmax(ans[i],sqrtl(sq(dif.a)+sq(dif.b))*wei);
				}
				
				auto rot=[&](P&v){
					int128 x=v.a+v.b;
					int128 y=-v.a+v.b;
					v.a=x;
					v.b=y;
				};
				for(auto&[a,b]:ls){
					rot(a);
					rot(b);
				}
				for(auto&[a,b]:qs){
					rot(a);
					rot(b);
				}
			}
		}else{
			dmp("No 45");
			
			Mirrors vert,hori;
			
			rep(i,n){
				P dir=ls[i].b-ls[i].a;
				if(dir.a==0){
					vert.add(ls[i].a.a);
				}else if(dir.b==0){
					hori.add(ls[i].a.b);
				}else assert(false);
			}
			vert.init();
			hori.init();
			
			auto work=[&](P&v){
				vert.fund(v.a);
				hori.fund(v.b);
			};
			
			rep(i,q){
				auto [a,b]=qs[i];
				work(a);
				work(b);
				P dif=a-b;
				ans[i]=sqrtl(sq(dif.a)+sq(dif.b));
			}
		}
	}
	ld D=sqrtl(sq(Xaxis.a)+sq(Xaxis.b));
	rep(i,q){
		ans[i]/=D;
		if(ans[i]>1e-10) puts("No");
		else puts("Yes");
	}
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	if(dbg){
		while(1)slv();
	}else{
		int t;cin>>t;rep(_,t)
		slv();
	}
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3840kb

input:

2
3
0 0 1 0
0 0 0 1
0 2 2 0
4
1 0 2 3
1 -2 -1 2
1 1 -1 0
3 3 3 3
3
0 0 1 0
0 0 0 1
-2 1 2 3
2
2 1 -1 5
-1 -1 3 3

output:

Yes
Yes
No
Yes
Yes
Yes

result:

ok 6 token(s): yes count is 5, no count is 1

Test #2:

score: 0
Accepted
time: 5ms
memory: 3912kb

input:

10
550
0 0 1 0
0 0 0 1
1070451 -76747419 -475756 34109964
39212129 -40187389 32082651 -32880591
-42770825 49053520 -51324990 58864224
301020 -10533714 602040 -21067428
-55137616 74952624 -24122707 32791773
1629975 -29851650 -478126 8756484
80523100 20960200 -77302176 -20121792
-64028006 61179727 -18...

output:

Yes
No
No
Yes
Yes
No
Yes
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
Yes
Yes
No
Yes
No
No
No
No
No
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
No
No
Yes
Yes
Yes
No
No
No
Yes
No
Yes
Ye...

result:

ok 12244 token(s): yes count is 6128, no count is 6116

Test #3:

score: 0
Accepted
time: 98ms
memory: 4112kb

input:

100
2000
0 0 1 0
0 0 0 1
-84998108 27087723 -78459792 25004052
-63732795 -93286980 29741971 43533924
88160702 10753904 -94457895 -11522040
-57759240 -99131840 25991658 44609328
-35408095 31386545 -92061047 81605017
21178080 37382229 32943680 58150134
-57187533 84956404 -17596164 26140432
38432164 17...

output:

No
No
No
Yes
Yes
Yes
No
Yes
No
No
Yes
No
No
No
Yes
No
No
Yes
No
Yes
No
No
No
No
No
No
Yes
No
Yes
No
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No
No
No
Yes
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
N...

result:

ok 200000 token(s): yes count is 100141, no count is 99859

Test #4:

score: 0
Accepted
time: 73ms
memory: 4164kb

input:

90
1025
0 0 1 0
0 0 0 1
-8716657 -748858 12990792 -22456307
-13593063 -23283552 -46628353 -23283552
93002789 28574481 93002789 78693002
-16042487 47828662 -30013237 61799412
43359811 68260568 43359811 -75987953
-94388305 52022201 -94388305 8537759
-6363687 -1383673 -6363687 -20211179
-29739675 -2602...

output:

Yes
No
No
No
Yes
No
Yes
Yes
No
Yes
No
No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
No
Yes
No
Yes
No
N...

result:

ok 111911 token(s): yes count is 30198, no count is 81713

Test #5:

score: 0
Accepted
time: 49ms
memory: 3896kb

input:

60
1827
0 0 1 0
0 0 0 1
-17538300 -17990820 -3024627 -3477147
1931426 28295794 -7230316 37457536
-50091040 -61102720 -50091040 -81287891
-8748721 7610399 -3122974 13236146
-11031224 10681644 26710340 -27059920
24141834 -4020934 30472616 -10351716
-34145900 53640301 -34145900 50102047
-9267760 282286...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Ye...

result:

ok 72683 token(s): yes count is 7452, no count is 65231

Test #6:

score: 0
Accepted
time: 55ms
memory: 3892kb

input:

60
1997
0 0 1 0
0 0 0 1
69327545 -42290317 69327545 63981221
-58631846 -15683378 -58631846 18914662
4797598 12519123 -29048979 46365700
9216180 2556055 20722330 -8950095
-36543647 35024712 -35771895 35024712
-10489112 91685408 -10489112 -57484395
6794531 26436588 6794531 -20764239
-26423402 -4976896...

output:

Yes
No
No
Yes
Yes
No
No
Yes
Yes
Yes
No
No
Yes
No
Yes
No
No
Yes
No
No
Yes
No
Yes
No
No
No
No
No
Yes
No
Yes
Yes
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
Yes
Yes
Yes
No
No
Yes
Yes
No
No
No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
No
Yes
No
No
Yes
No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
No
Yes
Yes
Yes
N...

result:

ok 79849 token(s): yes count is 8192, no count is 71657

Test #7:

score: 0
Accepted
time: 46ms
memory: 4092kb

input:

60
807
0 0 1 0
0 0 0 1
69990110 52698324 58640751 52698324
-6015050 2800994 -4061102 4754942
67806960 -10866065 67806960 78717943
-66237090 -99083936 83175963 -99083936
-89057656 -95080370 64126205 -95080370
-74320306 14980336 61936095 14980336
-4691148 24838238 -13069432 33216522
-44184536 34829110...

output:

Yes
Yes
Yes
Yes
No
No
No
No
Yes
No
Yes
No
No
Yes
No
No
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
Yes
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
Yes
Yes
No
Yes
No
No
No
Yes
No
No
Yes
No
No
No
No
No
Yes
Yes
No
Yes
No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
Yes
No
No
Yes
No
No
Yes
Yes
Yes
No
Yes
No
No...

result:

ok 71776 token(s): yes count is 21769, no count is 50007

Test #8:

score: 0
Accepted
time: 50ms
memory: 4068kb

input:

60
1891
0 0 1 0
0 0 0 1
-9198393 -8883107 31549745 -49631245
11096271 -8799824 34381579 -8799824
79393665 44942616 5266446 44942616
80038104 59629280 80038104 -73960991
59670664 95699832 59670664 -81538173
-73541249 -26052008 -16573483 -26052008
60296113 60318720 60104916 60318720
46427576 8929327 4...

output:

Yes
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
Yes
No
No
No
No
No
No
Yes
No
No
...

result:

ok 72035 token(s): yes count is 14238, no count is 57797

Test #9:

score: 0
Accepted
time: 38ms
memory: 3804kb

input:

55
682
0 0 1 0
0 0 0 1
-17023944 6375984 -32126895 21478935
-8975753 -17499359 -25464803 -1010309
-29768060 -42931964 2968852 -10195052
20010198 8113370 21431358 6692210
-10855708 -19806860 -30869619 207051
10554553 1985831 -11026795 23567179
21880938 -5953302 -28304390 -56138630
7753068 -29186348 -...

output:

No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 69726 token(s): yes count is 15879, no count is 53847

Test #10:

score: 0
Accepted
time: 139ms
memory: 3912kb

input:

100
2000
0 0 1 0
0 0 0 1
11659007 -12317071 21489140 -2486938
-82315139 90329884 -29802604 90329884
53186946 50733878 53186946 41692310
-26440204 65035919 -26440204 -65223934
7444254 -6850298 -10866206 -25160758
23235570 -41755929 -27157227 8636868
38843792 -25255333 51413751 -25255333
-95459342 741...

output:

No
Yes
No
No
Yes
No
Yes
No
No
Yes
Yes
No
Yes
No
No
No
No
No
No
No
Yes
Yes
No
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
No
Yes
Yes
No
No
Yes
Yes
Yes
No
No
No
No
No
No
Yes
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
No
Yes
No
No
No
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
No
No
Yes
Yes...

result:

ok 200000 token(s): yes count is 99988, no count is 100012

Test #11:

score: 0
Accepted
time: 37ms
memory: 3828kb

input:

64
2
0 0 1 0
0 0 0 1
2000
0 0 0 0
0 0 0 1
0 0 0 2
0 0 0 3
0 0 0 4
0 0 1 0
0 0 1 1
0 0 1 2
0 0 1 3
0 0 1 4
0 0 2 0
0 0 2 1
0 0 2 2
0 0 2 3
0 0 2 4
0 0 3 0
0 0 3 1
0 0 3 2
0 0 3 3
0 0 3 4
0 0 4 0
0 0 4 1
0 0 4 2
0 0 4 3
0 0 4 4
0 1 0 0
0 1 0 1
0 1 0 2
0 1 0 3
0 1 0 4
0 1 1 0
0 1 1 1
0 1 1 2
0 1 1 3
0 ...

output:

Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No...

result:

ok 128000 token(s): yes count is 83457, no count is 44543

Test #12:

score: 0
Accepted
time: 33ms
memory: 3900kb

input:

64
2
0 0 1 0
0 0 0 1
2000
0 0 0 0
0 0 0 1
0 0 0 2
0 0 0 3
0 0 0 4
0 0 1 0
0 0 1 1
0 0 1 2
0 0 1 3
0 0 1 4
0 0 2 0
0 0 2 1
0 0 2 2
0 0 2 3
0 0 2 4
0 0 3 0
0 0 3 1
0 0 3 2
0 0 3 3
0 0 3 4
0 0 4 0
0 0 4 1
0 0 4 2
0 0 4 3
0 0 4 4
0 1 0 0
0 1 0 1
0 1 0 2
0 1 0 3
0 1 0 4
0 1 1 0
0 1 1 1
0 1 1 2
0 1 1 3
0 ...

output:

Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No...

result:

ok 128000 token(s): yes count is 2740, no count is 125260

Test #13:

score: 0
Accepted
time: 34ms
memory: 4064kb

input:

50
695
0 0 1 0
0 0 0 1
84969345 46309479 -19636708 46309479
-66531791 -54688570 -51537863 -54688570
26880965 73917748 26880965 -74449331
-73557247 -48395973 -73557247 -46283294
59017748 68554941 -22405920 68554941
56629168 -99311739 56629168 39763583
22171753 64502030 -7298030 64502030
15051158 6510...

output:

No
No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
Yes
No
No
Yes
No
Yes
Yes
No
No
No
Yes
No
No
Yes
No
No
No
Yes
No
No
No
Yes...

result:

ok 62260 token(s): yes count is 5860, no count is 56400

Test #14:

score: 0
Accepted
time: 49ms
memory: 3980kb

input:

81
1685
0 0 1 0
0 0 0 1
-24922258 -1485441 72370623 -1485441
-26368698 39136545 -7459275 39136545
-77491241 57649041 -94929234 57649041
-6377599 49125798 -432086 49125798
63451733 28157130 8873357 28157130
9303882 98734869 -64726244 98734869
-32084278 -79535286 96025642 -79535286
34179465 37397655 3...

output:

No
No
No
No
No
No
No
Yes
Yes
No
No
No
Yes
Yes
No
No
No
Yes
No
No
No
No
No
No
Yes
No
Yes
No
No
No
No
No
No
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
Yes
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
Yes
No
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
No
No
Yes
No
Yes
No
No
...

result:

ok 98522 token(s): yes count is 13171, no count is 85351

Test #15:

score: 0
Accepted
time: 110ms
memory: 4152kb

input:

100
2000
0 0 1 0
0 0 0 1
-20004442 43880085 -20004442 8707268
22640653 98128596 22640653 -16697924
-12117338 -2708598 96912588 -2708598
26773661 41656793 -32639265 41656793
10103899 51907070 10103899 35474629
32890303 -96679588 32890303 87133385
92746158 9472507 92746158 56335976
30718985 66774365 5...

output:

No
No
No
Yes
No
No
No
Yes
No
Yes
No
Yes
Yes
No
No
No
Yes
Yes
Yes
Yes
No
No
No
Yes
No
No
No
Yes
No
No
Yes
Yes
No
No
No
No
No
No
Yes
No
No
No
No
Yes
No
No
Yes
No
Yes
No
No
Yes
Yes
No
No
Yes
No
No
No
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
Yes
No
No
Yes
Yes
No
No
No
Yes
No
No
No...

result:

ok 200000 token(s): yes count is 49888, no count is 150112

Test #16:

score: 0
Accepted
time: 5ms
memory: 4008kb

input:

10
742
0 0 1 0
0 0 0 1
23843783 -25323740 -67563308 56613958
1394302 -54999280 -1593488 62856320
-22142890 60453519 6326540 -17272434
-15735873 -80095722 97984922 35804079
76247314 -59857490 65812497 -34171849
-45215983 89045988 -78192605 -24135410
-24691734 -44591106 45268179 81750361
-97295534 610...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 13215 token(s): yes count is 13215, no count is 0

Test #17:

score: 0
Accepted
time: 95ms
memory: 4180kb

input:

100
2000
0 0 1 0
0 0 0 1
5491510 27238550 -98433178 -18726371
64779583 -95528495 5028339 80588344
-54304616 618518 89243667 -57609303
93733585 -25563021 16589309 -28761000
-26358743 -44586422 91070869 -30029396
16470213 97502781 -44087353 -41098094
84213871 10784836 41554003 -88937188
-50096755 -921...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 200000 token(s): yes count is 200000, no count is 0

Extra Test:

score: 0
Extra Test Passed