QOJ.ac
QOJ
| ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
|---|---|---|---|---|---|---|---|
| #976 | #631844 | #9457. Prime Set | hos_lyric | ucup-team2279 | Failed. | 2024-10-13 22:21:53 | 2024-10-13 22:21:57 |
Details
Extra Test:
Accepted
time: 533ms
memory: 24420kb
input:
4 3000 1499 41 42 251 252 461 462 671 672 881 882 1091 1092 1301 1302 1511 1512 1721 1722 1931 1932 2141 2142 2351 2352 2561 2562 2771 2772 2981 2982 3191 3192 3401 3402 3611 3612 3821 3822 4031 4032 4241 4242 4451 4452 4661 4662 4871 4872 5081 5082 5291 5292 5501 5502 5711 5712 5921 5922 6131 6132 ...
output:
2998 3000 3000 1000
result:
ok 4 lines
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #631844 | #9457. Prime Set | ucup-team2279# | AC ✓ | 308ms | 18172kb | C++20 | 848b | 2024-10-12 10:34:49 | 2024-10-13 19:27:30 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N=3005,M=2e6+5;
int n,k,a[N],p[M],c[N],b[N];
vector<int> e[N];
bool dfs(int x,int v){
b[x]=v;
for(int y:e[x]) if(b[y]!=v){
b[y]=v;
if(!c[y]||dfs(c[y],v)){
c[y]=x;c[x]=y;
return 1;
}
}
return 0;
}
void solve(){
cin>>n>>k;
memset(c,-1,sizeof c);
memset(b,0,sizeof b);
for(int i=1;i<=n;i++) cin>>a[i],e[i].clear();
int s1=0,s2=0;
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(!p[a[i]+a[j]])
e[i].push_back(j),e[j].push_back(i),c[i]=c[j]=0;
for(int i=1;i<=n;i++) if(!c[i]&&dfs(i,i)) s1++;
for(int i=1;i<=n;i++) if(!c[i]) s2++;
cout<<(s1>=k?k*2:s1*2+min(k-s1,s2))<<"\n";
}
int main(){
cin.tie(0)->sync_with_stdio(0);
for(int i=2;i<M;i++) if(!p[i]) for(int j=i*2;j<M;j+=i) p[j]=1;
int t;
cin>>t;
while(t--) solve();
return 0;
}