QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#112131#6570. Who Watches the Watchmen?AvavaAvaWA 2ms3696kbC++146.3kb2023-06-10 09:45:112023-06-10 09:45:14

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-10 09:45:14]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3696kb
  • [2023-06-10 09:45:11]
  • 提交

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'