QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#594213#4637. Cell Towerlight_ink_dotsWA 27ms4520kbC++201.5kb2024-09-27 20:20:232024-09-27 20:20:24

Judging History

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

  • [2024-09-27 20:20:24]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:4520kb
  • [2024-09-27 20:20:23]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100],dsu[5];
string s;
map<unsigned long long,unsigned long long>f;
queue<unsigned long long>q;
unordered_set<string>ok;
unordered_set<unsigned long long>st;
vector<unsigned long long>v[100];
int find(int x){
	return dsu[x]==x? x:dsu[x]=find(dsu[x]);
}
int main(){
	for(int i=0;i<64;i++)
		scanf("%d",&a[i]);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		cin>>s,ok.insert(s);
	int I[4];
	for(I[0]=0;I[0]<64;I[0]++)
		for(I[1]=I[0]+1;I[1]<64;I[1]++)
			for(I[2]=I[1]+1;I[2]<64;I[2]++)
				for(I[3]=I[2]+1;I[3]<=64;I[3]++){
					int c=3;
					string s;
					unsigned long long S=(1llu<<I[0])|(1llu<<I[1])|(1llu<<I[2]);
					s.resize(3),s[0]=a[I[0]]+48,s[1]=a[I[1]]+48,s[2]=a[I[2]]+48;
					if(I[3]<64)
						c++,s=s+(char)(a[I[3]]+48),S|=1llu<<I[3];
					if(ok.find(s)==ok.end())
						continue;
					dsu[0]=0,dsu[1]=1,dsu[2]=2,dsu[3]=3;
					for(int u=0;u<c;u++)
						for(int v=u+1;v<c;v++)
							if(abs(I[u]/8-I[v]/8)+abs(I[u]%8-I[v]%8)<=1)
								dsu[find(u)]=find(v);
					if(find(0)==find(1)&&find(1)==find(2)&&(c==3||find(2)==find(3)))
						for(int c=0;c<4;c++)
							v[I[c]].emplace_back(S);
				}
	q.push(0),f[0]=1;
	while(!q.empty()){
		unsigned long long S=q.front(),T;
		q.pop();
		for(int i=0;i<64;i++)
			if(((S>>i)&1)==0){
				for(int j=0;j<v[i].size();j++)
					if((S&v[i][j])==0){
						T=S|v[i][j];
						if(f.count(T)==0)
							q.push(T);
						f[T]+=f[S];
					}
				break;
			}
	}
	printf("%llu\n",f[-1ull]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 25ms
memory: 3876kb

input:

1 1 1 1 2 3 3 3
0 4 4 4 2 2 2 3
0 0 5 5 6 6 7 7
0 9 5 5 6 8 7 7
9 9 9 1 6 8 8 8
3 1 1 1 2 2 2 2
4 5 6 0 0 4 4 3
7 8 9 0 0 4 3 3
16
1111
2222
3333
444
0000
5555
6666
7777
8888
9999
111
333
3456
789
3478
569

output:

2

result:

ok single line: '2'

Test #2:

score: -100
Wrong Answer
time: 27ms
memory: 4520kb

input:

2 0 1 2 3 3 3 0
1 2 1 4 1 3 0 1
1 1 3 0 0 2 3 4
4 1 3 3 4 0 3 4
3 2 0 3 3 0 2 1
4 4 3 3 4 1 2 4
1 0 2 4 0 0 2 4
3 1 0 3 3 4 0 3
1000
953
1289
0424
673
9845
811
6865
0695
388
037
974
101
2416
560
1847
6433
6461
5835
457
629
788
456
498
2762
223
013
418
945
3275
9724
7059
2075
0231
587
100
2420
0606
2...

output:

1227

result:

wrong answer 1st lines differ - expected: '1313', found: '1227'