QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#811060 | #9802. Light Up the Grid | rotcar07 | WA | 13ms | 4192kb | C++23 | 1.0kb | 2024-12-12 15:02:56 | 2024-12-12 15:03:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int a[4],f[1<<16];
constexpr pair<int,int> sk[]={{1,0},{2,0},{4,0},{8,0},{3,1},{12,1},{5,2},{10,2},{15,3}};
inline void solve(){
int m=0;int msk=0;
cin>>m;
while(m--){
char a,b,c,d;cin>>a>>b>>c>>d;
msk|=1<<((a-'0')+(b-'0')*2+(c-'0')*4+(d-'0')*8);
}
cout<<f[msk]<<'\n';
}
int main(){
std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;cin>>t>>a[0]>>a[1]>>a[2]>>a[3];
memset(f,0x3f,sizeof f);
priority_queue<pair<int,int>> q;q.emplace(0,1<<15);f[1<<15]=0;
while(!q.empty()){
auto [dis,p]=q.top();q.pop();dis=-dis;
if(f[p]!=dis) continue;
vector<int> v;
auto upd=[&](int to,int dis){if(f[to]>dis)f[to]=dis,q.emplace(-dis,to);};
for(int j=0;j<16;j++) if(p>>j&1) v.push_back(j);
for(auto [ff,y]:sk){
int to=1<<15;
for(int x:v) to|=1<<(x^ff);
upd(to,dis+a[y]);
}
}
for(int i=0;i<16;i++)
for(int j=0;j<1<<16;j++)if(j>>i&1)f[j^1<<i]=min(f[j^1<<i],f[j]);
f[1<<15]=2**min_element(a,a+4);
while(t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 13ms
memory: 4172kb
input:
2 1000 100 10 1 4 10 00 01 00 00 10 00 01 1 11 11
output:
1121 2
result:
ok 2 number(s): "1121 2"
Test #2:
score: 0
Accepted
time: 9ms
memory: 4000kb
input:
2 1 1 1 1 4 10 00 01 00 00 10 00 01 1 11 11
output:
5 2
result:
ok 2 number(s): "5 2"
Test #3:
score: 0
Accepted
time: 10ms
memory: 4192kb
input:
1 1000000 1000000 1000000 1000000 1 11 11
output:
2000000
result:
ok 1 number(s): "2000000"
Test #4:
score: -100
Wrong Answer
time: 13ms
memory: 3992kb
input:
10000 8 2 7 8 8 00 01 00 11 00 10 11 11 10 10 01 10 01 00 10 11 8 11 01 11 00 01 10 11 11 00 01 01 01 01 00 11 10 9 00 00 01 01 10 11 00 01 11 10 11 00 11 11 00 11 01 10 9 11 11 10 00 11 00 11 01 00 10 01 11 00 01 01 01 10 01 11 00 01 01 01 10 10 00 11 11 11 11 10 ...
output:
32 30 34 34 40 36 41 38 40 37 34 42 34 37 37 31 29 35 39 40 38 36 40 34 25 34 34 38 34 31 32 37 34 36 37 40 40 34 37 34 29 35 35 36 42 35 35 34 38 34 37 29 38 38 36 37 43 36 41 30 40 39 33 33 34 36 34 34 42 40 34 32 28 34 32 37 34 39 34 37 32 36 30 30 32 34 38 40 34 36 40 39 34 36 34 25 36 40 36 34 ...
result:
wrong answer 1st numbers differ - expected: '34', found: '32'