QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#672369 | #9172. Alternating Cycle | ucup-team1338 | WA | 1ms | 5892kb | C++14 | 6.8kb | 2024-10-24 16:37:21 | 2024-10-24 16:37:22 |
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5892kb
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: 5668kb
input:
4 0 0 0 1 1 0 1 1
output:
-1
result:
ok Everything ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3844kb
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: -100
Wrong Answer
time: 1ms
memory: 5672kb
input:
9 870407732 947373192 362190573 311657719 792350850 916217578 908809410 529664178 147184624 105531482 800863654 27569449 290489622 819212758 64484618 355712627 474856219 425123887
output:
-1
result:
wrong answer Jury has a better answer