QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#813918 | #9880. Origami Warp | ucup-team3161# | AC ✓ | 139ms | 4180kb | C++14 | 16.9kb | 2024-12-14 13:38:20 | 2024-12-14 13:38:25 |
Judging History
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,我给组数据试试?
詳細信息
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