QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #631844 | #9457. Prime Set | ucup-team2279# | AC ✓ | 308ms | 18172kb | C++20 | 848b | 2024-10-12 10:34:49 | 2024-10-13 19:27:30 |
Judging History
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;
}
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 100
Accepted
time: 22ms
memory: 11556kb
input:
4 4 2 2 3 4 5 5 3 3 4 12 3 6 6 3 1 3 6 8 1 1 1 0 1
output:
4 3 6 0
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 308ms
memory: 18172kb
input:
110 3 3 2 2 2 3 1 1 1 1 3 2 1 1 1 3 3 1 1 1 4 2 1 1 1 1 10 7 1 1 1 2 4 6 8 10 12 14 18 1 10 5 9 4 10 7 2 4 9 1 6 1 4 9 2 4 9 7 19 5 1 6 1 8 8 1 5 10 9 2 10 2 1 9 6 10 4 3 6 14 4 6 6 8 9 5 3 4 9 2 2 1 10 10 1 15 10 5 4 2 4 10 1 8 4 10 3 10 3 7 10 4 17 5 10 7 2 4 3 1 10 8 2 8 3 4 1 1 1 1 1 20 6 8 4 6 ...
output:
0 2 3 3 4 8 2 10 8 15 10 12 10 10 12 16 10 10 12 16 14 13 13 14 17 0 19 12 12 11 16 10 19 2 12 10 5 14 10 10 13 2 18 2 4 4 11 8 11 8 0 10 10 0 10 0 8 15 12 11 13 18 10 17 9 8 20 19 13 6 4 6 11 9 13 11 6 2 8 12 17 14 6 2 20 2 18 17 6 2 10 0 7 16 2 2 0 2 18 14 11 8 4 6 0 19 890 204 2746 2372
result:
ok 110 lines
Extra Test:
score: 0
Extra Test Passed