QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#594245 | #4637. Cell Tower | light_ink_dots | WA | 28ms | 4500kb | C++20 | 1.5kb | 2024-09-27 20:34:35 | 2024-09-27 20:34:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100],dsu[5];
string s;
unordered_set<string>ok;
map<unsigned long long,unsigned long long>f;
queue<unsigned long long>q;
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 i=0;i<c;i++)
v[I[i]].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: 28ms
memory: 4056kb
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: 4500kb
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'