QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#672374 | #9172. Alternating Cycle | ucup-team1338 | WA | 1ms | 5796kb | C++14 | 6.8kb | 2024-10-24 16:38:33 | 2024-10-24 16:38:33 |
Judging History
answer
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define int long long
#define ull unsigned long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define mod 998244353
struct modint{
int x;
modint(int o=0){x=o;}
modint &operator = (int o){return x=o,*this;}
modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
modint &operator ^=(int b){
modint a=*this,c=1;
for(;b;b>>=1,a*=a)if(b&1)c*=a;
return x=c.x,*this;
}
modint &operator /=(modint o){return *this *=o^=mod-2;}
friend modint operator +(modint a,modint b){return a+=b;}
friend modint operator -(modint a,modint b){return a-=b;}
friend modint operator *(modint a,modint b){return a*=b;}
friend modint operator /(modint a,modint b){return a/=b;}
friend modint operator ^(modint a,int b){return a^=b;}
friend bool operator ==(modint a,modint b){return a.x==b.x;}
friend bool operator !=(modint a,modint b){return a.x!=b.x;}
bool operator ! () {return !x;}
modint operator - () {return x?mod-x:0;}
bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}
vector<modint> fac,ifac,iv;
inline void initC(int n)
{
if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
int m=iv.size(); ++n;
if(m>=n)return;
iv.resize(n),fac.resize(n),ifac.resize(n);
For(i,m,n-1){
iv[i]=iv[mod%i]*(mod-mod/i);
fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
}
}
inline modint C(int n,int m){
if(m<0||n<m)return 0;
return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 800005
#define inf 0x3f3f3f3f
struct P{
int x,y,id;
P(int x=0,int y=0):x(x),y(y){}
P&operator +=(P o){return x+=o.x,y+=o.y,*this;}
P&operator -=(P o){return x-=o.x,y-=o.y,*this;}
P&operator *=(int o){return x*=o,y*=o,*this;}
P&operator /=(int o){return x/=o,y/=o,*this;}
friend P operator +(P a,P b){return a+=b;}
friend P operator -(P a,P b){return a-=b;}
friend P operator *(P a,int b){return a*=b;}
friend P operator /(P a,int b){return a/=b;}
friend bool operator <(P a,P b){return a.x==b.x?a.y<b.y:a.x<b.x;}
friend int operator %(P a,P b){return a.x*b.x+a.y*b.y;} // dot
friend int operator *(P a,P b){return a.x*b.y-a.y*b.x;} // cross
inline double ang(){return atan2(y,x);}
inline double l(){return sqrt((*this)*(*this));}
void read(){cin>>x>>y;}
void out(){cout<<"("<<x<<","<<y<<")"<<endl;}
};
int sgn(int x){
return x<0?-1:(x>0);
}
int cross(P a,P b,P c){
//(a->b) ---> (a->c)
return (b-a)*(c-a);
}
int cmp3(P a,P b,P c){
return sgn(cross(a,b,c));
}
int n,m;
vector<P>a,b,t;
bool vis[maxn];
vector<P>convex(vector<P>o){
sort(o.begin(),o.end());
int n=o.size();
vector<P>p;
For(i,0,n-1){
while(p.size()>1&&(p.back()-p[p.size()-2])*(o[i]-p[p.size()-2])<=0) p.pop_back();
p.pb(o[i]);
}
int m=p.size();
Rep(i,n-2,0){
while(p.size()>m&&(p.back()-p[p.size()-2])*(o[i]-p[p.size()-2])<=0) p.pop_back();
if(i)p.pb(o[i]);
}
return p;
}
void check(vector<P>o){
// cout<<"check\n";
int n=o.size();
vector<int>d(n);
For(i,0,n-1) d[i]=cmp3(o[i],o[(i+1)%n],o[(i+2)%n]);
// For(i,0,n-1) cout<<d[i]<<" "; cout<<"\n";
For(i,0,n-1) if(d[i]!=-d[(i+1)%n]) return;
cout<<o.size()<<"\n";
for(auto it:o)cout<<it.x<<" "<<it.y<<"\n";
exit(0);
}
bool in(P p,P a,P b,P c){
return cmp3(a,b,p)>0 && cmp3(b,c,p)>0 && cmp3(c,a,p)>0;
}
bool vis1[13],vis2[13];
vector<P>ans;
void dfs(int u){
if(u==6){
check(ans);
return;
}
if(u%2==0){
For(i,0,n-1) if(!vis1[i]) {
vis1[i]=1;
ans[u]=b[i];
dfs(u+1);
vis1[i]=0;
}
}else{
For(i,0,m-1) if(!vis2[i]){
vis2[i]=1;
ans[u]=t[i];
dfs(u+1);
vis2[i]=0;
}
}
}
void solve3(){
// for(auto it:b)it.out();puts("---b---");
// for(auto it:t)it.out();puts("---t---");
while(b.size()>6){
n=b.size();
bool fd=0;
Rep(i,n-1,0){
P A=b[(i+n-1)%n],B=b[i],C=b[(i+1)%n];
bool ok=1;
for(auto p:t)
if(in(p,A,B,C)) ok=0;
if(ok){
For(j,i,n-2) b[j]=b[j+1];
b.pop_back();
fd=1;
break;
}
}
assert(fd);
}
// for(auto it:b)it.out();puts("---b---");
// for(auto it:t)it.out();puts("---t---");
n=b.size();
m=t.size();
ans.resize(6);
dfs(0);
puts("-1"),exit(0);
assert(0);
}
namespace S2{
int op[maxn],n;
P A,B;
vector<P>p,q;
bool solve2(vector<P>b,vector<P>t){
n=b.size();
A=t[0],B=t[1];
int c1=0,c2=0;
For(i,0,n-1) op[i]=cmp3(A,B,b[i]),c1+=(op[i]>0),c2+=(op[i]<0);
if(c1<=1 || c2<=1) return 0;
For(i,0,n-1) if(op[(i+n-1)%n]==-1 && op[i]==1){
for(int j=i;op[j]==1;j=(j+1)%n) p.pb(b[j]);
break;
}
For(i,0,n-1) if(op[(i+n-1)%n]==1 && op[i]==-1){
for(int j=i;op[j]==-1;j=(j+1)%n) q.pb(b[j]);
break;
}
// assert(p.size()>=2 && q.size()>=2);
P p1,p2,q1,q2;
int np=p.size(),nq=q.size();
int j=nq-1;
bool ok=0;
Rep(i,np-1,0){
while(j>=0 && cmp3(p[i],B,q[j])>0) --j;
if(j>=0 && cmp3(p[i],A,q[j])>0){
p1=p[i],q1=q[j];
ok=1;
break;
}
}
if(!ok) return 0;
j=0;
ok=0;
For(i,0,nq-1){
while(j<=np-1 && cmp3(q[i],B,p[j])<0) ++j;
if(j<=np-1 && cmp3(q[i],A,p[j])<0){
q2=q[i],p2=p[j];
ok=1;
break;
}
}
if(!ok) return 0;
vector<P>tmp={p1,A,q2,p2,B,q1};
For(i,0,5)For(j,i+1,5)if(tmp[i].id==tmp[j].id) return 0;
check(tmp);
return 0;
}
}
signed main()
{
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
n=read();
a.resize(n);
For(i,0,n-1)a[i].x=read(),a[i].y=read(),a[i].id=i;
b=convex(a);
for(auto t:b) vis[t.id]=1;
int cnt=0;
For(i,0,n-1)cnt+=(!vis[i]);
if(cnt<=1){
puts("-1");
exit(0);
}
vector<P>aa;
for(auto t:a) if(!vis[t.id] && aa.size()<3) aa.pb(t);
::t=aa;
if(cnt==2){
//S2::solve2(b,t);
puts("-1");
exit(0);
}
For(i,0,2) For(j,i+1,2) S2::solve2(b,vector<P>{t[i],t[j]});
solve3();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5688kb
input:
6 10 15 20 15 15 23 0 31 15 0 30 30
output:
6 0 31 10 15 15 0 20 15 30 30 15 23
result:
ok Everything ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 5796kb
input:
4 0 0 0 1 1 0 1 1
output:
-1
result:
ok Everything ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
9 693150551 810053304 26684055 999173154 767007508 725151476 697948407 601311897 593914132 156628727 294286621 249587903 361249906 42266067 110658137 698550461 923704821 886066345
output:
6 26684055 999173154 693150551 810053304 923704821 886066345 767007508 725151476 593914132 156628727 697948407 601311897
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
9 870407732 947373192 362190573 311657719 792350850 916217578 908809410 529664178 147184624 105531482 800863654 27569449 290489622 819212758 64484618 355712627 474856219 425123887
output:
6 147184624 105531482 362190573 311657719 800863654 27569449 290489622 819212758 792350850 916217578 870407732 947373192
result:
ok Everything ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
9 47664912 379660370 66293309 34207701 186290410 443720168 456106901 458016459 995422410 349401528 602407977 731922069 588325559 932595937 608245683 644278574 657411398 627744942
output:
6 47664912 379660370 186290410 443720168 588325559 932595937 602407977 731922069 995422410 349401528 456106901 458016459
result:
ok Everything ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
9 224922093 516980257 696767119 51724974 580229972 266190050 593338977 91401448 843660194 888238866 108985009 509903616 591194203 709542627 225635675 932844521 618628214 461769776
output:
6 108985009 509903616 224922093 516980257 593338977 91401448 580229972 266190050 843660194 888238866 591194203 709542627
result:
ok Everything ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
9 107211982 359332853 695837148 142871176 605573313 162288860 509232688 314721021 396930687 132108911 205496625 287885162 183997430 822925807 474429448 221410467 801183393 664390830
output:
6 396930687 132108911 605573313 162288860 695837148 142871176 107211982 359332853 509232688 314721021 801183393 664390830
result:
ok Everything ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
9 284469163 791620032 31343664 160388450 294480166 689791450 351497471 948106011 245168471 81011666 7040948 65866709 481833366 304905205 91819440 215009122 983738573 203448372
output:
6 7040948 65866709 294480166 689791450 351497471 948106011 481833366 304905205 983738573 203448372 91819440 215009122
result:
ok Everything ok
Test #9:
score: 0
Accepted
time: 1ms
memory: 5668kb
input:
9 461726344 560343699 661817474 882938432 319823507 217294040 562358475 876458292 93406256 619849004 513617981 138815548 484702011 418288384 340613213 503575069 534889971 406069427
output:
6 93406256 619849004 461726344 560343699 661817474 882938432 484702011 418288384 513617981 138815548 340613213 503575069
result:
ok Everything ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
9 638983525 992630879 660887503 900455706 713763069 113392850 404623258 99777864 646676749 863719050 315162304 548200875 782537947 195235074 958003206 160737235 422477859 945126970
output:
6 638983525 992630879 646676749 863719050 422477859 945126970 958003206 160737235 782537947 195235074 713763069 113392850
result:
ok Everything ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
9 521273414 129950765 291361311 623005687 107702630 935862733 320516969 733162854 494914533 812621805 453143117 621149714 711777663 308618254 206796978 449303183 678661966 147748023
output:
6 107702630 935862733 291361311 623005687 521273414 129950765 453143117 621149714 494914533 812621805 320516969 733162854
result:
ok Everything ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
8 563402439 725563321 430451262 152240853 780848346 860389268 888894820 499849356 415818421 408692535 840472921 429397462 326582722 561795426 53848834 517062841
output:
6 53848834 517062841 563402439 725563321 780848346 860389268 415818421 408692535 430451262 152240853 326582722 561795426
result:
ok Everything ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
8 740659620 157850500 839586707 169758127 469755198 387891858 436192311 428201637 264056205 652562581 936984536 838782790 624418658 970145897 966206119 805628788
output:
-1
result:
ok Everything ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
8 917916801 295170387 470060516 892308109 495098540 283990668 647053314 356553918 817326699 191399918 443561568 911731629 922254594 157158003 920032600 94194734
output:
-1
result:
ok Everything ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
8 800206690 432490275 469130545 909825383 889038101 106460550 489318097 284906199 665564483 140302673 245105891 689713175 925123238 565508474 832389884 456389610
output:
-1
result:
ok Everything ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
8 272431162 201213942 99604353 632375365 914381443 338995849 700179101 213258480 218834975 384172719 751682924 762662014 222959174 47487873 786216365 744955557
output:
-1
result:
ok Everything ok
Test #17:
score: 0
Accepted
time: 1ms
memory: 5660kb
input:
8 154721052 338533829 803707091 18488857 308321004 530061950 542443884 141610761 772105469 628042765 553227248 540643561 447166182 455838344 698573649 33521503
output:
6 154721052 338533829 542443884 141610761 698573649 33521503 308321004 530061950 553227248 540643561 772105469 628042765
result:
ok Everything ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
8 331978233 475853717 434180900 741038840 997227857 57564540 384708667 774995751 620343253 871912811 354771571 950028888 450034826 937817743 947367422 322087450
output:
-1
result:
ok Everything ok
Test #19:
score: 0
Accepted
time: 1ms
memory: 5604kb
input:
8 214268122 908140896 64654708 758556113 727603907 585067131 595569671 998315324 468581038 115782857 861348604 728010435 747870762 346168213 196161194 610653397
output:
-1
result:
ok Everything ok
Test #20:
score: -100
Wrong Answer
time: 0ms
memory: 3608kb
input:
8 686492595 45460782 63724737 776073387 121543467 776133233 142867162 926667605 21851530 359652903 589263999 800959274 45706698 828147612 108518478 267815563
output:
-1
result:
wrong answer Jury has a better answer