QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#112131 | #6570. Who Watches the Watchmen? | AvavaAva | WA | 2ms | 3696kb | C++14 | 6.3kb | 2023-06-10 09:45:11 | 2023-06-10 09:45:14 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
namespace mcmf
{
const int N=5005,M=1000005,inf=1e9;
int head[N],eid=1,ans,cost,dep[N],s=2001,t=2002,vis[N],dis[N],lst[N];
struct edge
{
int u,v,w,c,fl,n;
}e[M*2];
inline void add(int u,int v,int w,int c)
{
// cout << u << " " << v << " " << w << "\n";
e[++eid]={u,v,w,c,0,head[u]},head[u]=eid;
e[++eid]={v,u,0,-c,0,head[v]},head[v]=eid;
}
inline void go()
{
int now=t,mn=inf;
while(now!=s)
{
mn=min(mn,e[lst[now]].w-e[lst[now]].fl);
now=e[lst[now]].u;
}
ans+=mn,cost+=dis[t]*mn;
now=t;
while(now!=s)
{
e[lst[now]].fl+=mn,e[lst[now]^1].fl-=mn;
now=e[lst[now]].u;
}
}
inline bool spfa()
{
queue <int> q;
for(int i=0;i<N;i++) vis[i]=0,dis[i]=inf;
dis[s]=0,q.push(s),vis[s]=1;
while(!q.empty())
{
int x=q.front();
q.pop(),vis[x]=0;
for(int i=head[x];i;i=e[i].n)
{
if(e[i].w!=e[i].fl)
{
if(dis[e[i].v]>dis[x]+e[i].c)
{
dis[e[i].v]=dis[x]+e[i].c,lst[e[i].v]=i;
if(!vis[e[i].v]) q.push(e[i].v),vis[e[i].v]=1;
}
}
}
}
if(dis[t]==inf) return 0;
return 1;
}
inline void mcmf()
{
while(spfa()) go();
}
}
mt19937_64 rnd(22625025);
ull Rnd[3];
struct point
{
int x,y,z;
friend point operator +(point x,point y)
{
return {x.x+y.x,x.y+y.y,x.z+y.z};
}
friend point operator -(point x,point y)
{
return {x.x-y.x,x.y-y.y,x.z-y.z};
}
ull hsh()
{
return x*Rnd[0]+y*Rnd[1]+z*Rnd[2];
}
}a[505],b[505];
int D(point x)
{
return (x.x*x.x+x.y*x.y+x.z*x.z);
}
point qwq(point x)
{
int G=__gcd(__gcd(x.x,x.y),x.z);
if(G<0) G*=-1;
x.x/=G;
x.y/=G;
x.z/=G;
return x;
}
int dis[505][505],Id;
bool cmp(int x,int y)
{
return dis[Id][x]<dis[Id][y];
}
vector<pair<int,int> > E[505];
int okl[505],okr[505],w[505][505];
ull Hb[505];
int sl[505],sr[505];
bool qaq(point x,point y,point z)
{
if(D(x)<D(y)) swap(x,y);
if(D(y)<D(z)) swap(y,z);
if(D(x)<D(y)) swap(x,y);
int a=x.x,b=x.y,c=x.z;
int d=y.x,e=y.y,f=y.z;
int g=z.x,h=z.y,i=z.z;
if((a*e*i-a*h*f-d*b*i+d*h*c+g*b*f-g*e*c)!=0) return 0;
/* cout << a << " " << b << " " << c << "\n";
cout << d << " " << e << " " << f << "\n";
cout << g << " " << h << " " << i << "\n";
cout << "QWQ?\n";*/
int xA=d*h-e*g,xB=d*b-e*a;
int yA=a*h-b*g,yB=a*e-b*d;
// cout << xA << " " << xB << " " << yA << " " << yB << "\n";
if(xA==0||xB==0||yA==0||yB==0) return 0;
if((xA>0)!=(xB>0)) return 0;
if((yA>0)!=(yB>0)) return 0;
return 1;
}
int cal(int x,int y,int z)
{
int rtn=1e9;
int k=0;
k+=sl[z]-sl[x];
if(okr[x]||okl[x])
{
if(okr[y]||okl[y]) k+=2;
else k+=1;
}
else
{
if(okr[y]||okl[y]) k++;
else
{
// cout << b[x].x << " " << b[x].y << " " << b[x].z << "!\n";
// cout << b[y].x << " " << b[y].y << " " << b[y].z << "!\n";
point t=a[z]-a[x];
// cout << a[x].x << " " << a[x].y << " " << a[x].z << "!\n";
// cout << a[z].x << " " << a[z].y << " " << a[z].z << "!\n";
// cout << t.x << " " << t.y << " " << t.z << "!\n";
if(Hb[x]!=Hb[y]&&qaq(b[x],b[y],a[z]-a[x]));
else ++k;
}
}
rtn=min(rtn,k);
k=0;
k+=sr[z-1]-sr[x-1];
swap(x,z);
if(okr[x]||okl[x])
{
if(okr[y]||okl[y]) k+=2;
else k+=1;
}
else
{
if(okr[y]||okl[y]) k++;
else
{
if(Hb[x]!=Hb[y]&&qaq(b[x],b[y],a[z]-a[x]));
else ++k;
}
}
return min(rtn,k);
}
signed main()
{
Rnd[0]=rnd();
Rnd[1]=rnd();
Rnd[2]=rnd();
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
if(n==1)
{
cout << -1;
return 0;
}
for(int i=1;i<=n;i++)
{
cin >> a[i].x >> a[i].y >> a[i].z;
cin >> b[i].x >> b[i].y >> b[i].z;
b[i]=qwq(b[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
dis[i][j]=(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z);
}
for(int i=1;i<=n;i++) mcmf::add(mcmf::s,i,1,0),mcmf::add(i+n,mcmf::t,1,0);
for(int i=1;i<=n;i++)
{
int p[505];
for(int j=1;j<=n;j++) p[j]=j;
Id=i;
sort(p+1,p+n+1,cmp);
set<ull> S;
// cout << dis[3][1] << " " << dis[3][2] << "qwq\n";
for(int J=1;J<=n;J++)
{
int j=p[J];
// cout << i << " " << j << "\n";
if(i==j) continue;
point k=qwq(a[j]-a[i]);
ull H=k.hsh();
if(S.find(H)!=S.end()) continue;
S.insert(H);
if(k.x==b[i].x&&k.y==b[i].y&&k.z==b[i].z)
mcmf::add(i,j+n,1,0),E[i].push_back({j,0});
mcmf::add(i,j+n,1,1),E[i].push_back({j,1});
}
}
mcmf::mcmf();
if(mcmf::ans==n)
{
cout << mcmf::cost;
return 0;
}
for(int i=1;i<=n;i++)
{
if(E[i].size()==1)
{
queue<int> q;
int vis[1005]={};
q.push(i),vis[i]=1;
vector<int> s;
while(!q.empty())
{
int x=q.front();
q.pop(),s.push_back(x);
for(auto v:E[x])
if(!vis[v.first]) vis[v.first]=1,q.push(v.first);
}
point A[505],B[505];
for(int i=0;i<s.size();i++)
A[i+1]=a[s[i]],B[i+1]=b[s[i]];
for(int i=1;i<=n;i++) a[i]=A[i],b[i]=B[i];
break;
}
}
ull dr=qwq(a[2]-a[1]).hsh(),dl=qwq(a[1]-a[2]).hsh();
for(int i=1;i<=n;i++)
{
Hb[i]=qwq(b[i]).hsh();
if(qwq(b[i]).hsh()==dr) okr[i]=1;
if(qwq(b[i]).hsh()==dl) okl[i]=1;
sl[i]=sl[i-1]+1-okl[i];
sr[i]=sr[i-1]+1-okr[i];
}
for(int l=1;l<=n;l++)
{
int t=0;
for(int r=l;r<=n;r++)
{
if((r-l)&1) t+=1-okl[r];
else t+=1-okr[r];
w[l][r]=t;
}
}
int ans=1e7;
for(int x=1;x<=n;x++)
{
for(int y=1;y<=n;y++)
{
if(x==y) continue;
if(((x-1)-(y<=x))&1) continue;
// cout << x << " " << y << "\n";
for(int z=x;z<=n;z++)
{
if(z==x||z==y) continue;
if(((n-z)-(y>=z))&1) continue;
// cout << x << " " << y << " " << z << "\n";
int k=0;
--x;
if(y>x) k+=w[1][x];
else
{
if(y%2==0) k+=w[1][y-1]+(w[2][x]-w[2][y]);
else k+=w[1][y-1]+w[y+1][x];
}
++x;
++z;
if(y<z) k+=w[z][n];
else k+=w[z][y-1]+(w[z+1][n]-w[z+1][y]);
--z;
if(k>=ans) continue;
// cout << k << "!\n";
ans=min(ans,cal(x,y,z)+k);
}
}
}
cout << ans+1000;
return 0;
}
/*
4
0 0 0 1 1 1
2 2 2 1 1 1
1 1 1 -1 -1 -1
3 3 3 -1 -1 -1
2
3
0 0 0 1 1 2
2 2 2 1 2 1
1 1 1 2 1 1
3
0 0 0 -1 -1 -1
2 2 2 1 1 1
1 1 1 1 1 1
3
0 0 0 0 1 1
0 1 1 0 0 -1
0 2 2 0 -1 0
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3696kb
input:
7 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 1 0 0 3 0 0 1 0 0 4 0 0 1 0 0 5 0 0 1 0 0 6 0 0 -1 0 0
output:
1002
result:
ok single line: '1002'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
4 66 45 10 73 39 36 95 14 26 47 84 59 14 66 89 89 36 78 16 27 94 79 24 24
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
3 0 0 0 1 0 0 1 1 1 1 0 0 2 2 2 1 0 0
output:
1002
result:
ok single line: '1002'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
3 0 0 0 1 1 1 1 1 1 1 0 0 2 2 2 1 0 0
output:
1001
result:
ok single line: '1001'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
3 0 0 0 1 0 0 1 1 1 1 0 0 2 2 2 -1 -1 -1
output:
1001
result:
ok single line: '1001'
Test #6:
score: -100
Wrong Answer
time: 2ms
memory: 3556kb
input:
3 0 0 0 1 0 0 1 1 1 1 2 2 2 2 2 -1 -1 -1
output:
1001
result:
wrong answer 1st lines differ - expected: '1000', found: '1001'