QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #633535 | #9457. Prime Set | ucup-team4474# | AC ✓ | 77ms | 29384kb | C++20 | 5.4kb | 2024-10-12 15:40:23 | 2024-10-13 19:27:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
bool Memory_begin;
/*
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
1
4 2
5 1 8 6
*/
const int N = 2e6 + 5;
int is_prime[N], pri[N], tot;
bool Memory_end;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cerr << (&Memory_end - &Memory_begin) / 1048576.0 << "MB" << '\n';
for (int i = 2; i < N; i++)
{
if (!is_prime[i])
pri[++tot] = i;
for (int j = 1; j <= tot and pri[j] * i < N; j++)
{
is_prime[i * pri[j]] = 1;
if (i % pri[j] == 0)
break;
}
}
is_prime[2] = 1;
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
int s = 0, t = n + 1;
vector<int> head(t + 1, -1), nxt, to, cap;
auto add = [&](int x, int y)
{
to.push_back(y);
cap.push_back(1);
nxt.push_back(head[x]);
head[x] = to.size() - 1;
to.push_back(x);
cap.push_back(0);
nxt.push_back(head[y]);
head[y] = to.size() - 1;
};
vector<int> dis(t + 1), g(t + 1);
auto bfs = [&]() -> bool
{
dis.assign(t + 1, -1);
dis[s] = 0;
queue<int> que;
que.push(s);
while (!que.empty())
{
int cur = que.front();
que.pop();
g[cur] = head[cur];
for (int p = head[cur]; ~p; p = nxt[p])
{
if (dis[to[p]] == -1 and cap[p])
{
dis[to[p]] = dis[cur] + 1;
que.push(to[p]);
}
}
}
return dis[t] != -1;
};
auto dfs = [&](auto &dfs, int cur, int flow) -> int
{
if (cur == t)
return flow;
int used = 0;
for (int &p = g[cur]; ~p; p = nxt[p])
{
if (dis[to[p]] == dis[cur] + 1 and cap[p])
{
int tmp = dfs(dfs, to[p], min(flow - used, cap[p]));
used += tmp;
cap[p] -= tmp, cap[p ^ 1] += tmp;
if (used == flow)
break;
}
}
return used;
};
int ans = 0;
vector<int> vis(n + 1);
for (int i = 1; i <= n; i++)
{
if (a[i] == 1 or a[i] % 2 == 0)
continue;
for (int j = 1; j <= n; j++)
{
if (a[j] % 2 == 1 or !is_prime[a[j] + 1])
continue;
if (is_prime[a[i] + a[j]])
continue;
if (!vis[i])
{
add(s, i);
vis[i] = 1;
}
if (!vis[j])
{
add(j, t);
vis[j] = 1;
}
add(i, j);
}
}
while (k and bfs())
{
int tmp = dfs(dfs, s, k);
ans += tmp * 2;
k -= tmp;
}
for (int i = 1; i <= n; i++)
{
if (a[i] == 1 or a[i] % 2 == 0)
continue;
for (int j = 1; j <= n; j++)
{
if (a[j] % 2 == 1 or is_prime[a[j] + 1])
continue;
if (is_prime[a[i] + a[j]])
continue;
if (!vis[i])
{
add(s, i);
vis[i] = 1;
}
if (!vis[j])
{
add(j, t);
vis[j] = 1;
}
add(i, j);
}
}
while (k and bfs())
{
int tmp = dfs(dfs, s, k);
ans += tmp * 2;
k -= tmp;
}
vector<int> can;
for (int p = head[s]; ~p; p = nxt[p])
if (cap[p])
can.push_back(to[p]);
for (int p = head[t]; ~p; p = nxt[p])
if (!cap[p])
can.push_back(to[p]);
int c1 = 0;
for (int i = 1; i <= n; i++)
c1 += (a[i] == 1);
for (int i = 1; i <= n; i++)
if (a[i] != 1 and head[i] == -1 and c1 and !is_prime[a[i] + 1])
can.push_back(i);
int c0 = 0, fg = 0;
if (c1 >= 2)
fg = 1;
for (int i = 1; i <= n; i++)
if (a[i] != 1 and c1 and !is_prime[a[i] + 1])
fg = 1;
while (!can.empty())
{
int cur = can.back();
can.pop_back();
if (k and c1 and !is_prime[a[cur] + 1])
{
k -= 1;
c1 -= 1;
ans += 2;
}
else
c0 += 1;
}
while (c1 >= 2 and k)
{
ans += 2;
c1 -= 2;
k -= 1;
}
if (fg)
c0 += c1;
ans += min(k, c0);
cout << ans << '\n';
}
}
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 6ms
memory: 12220kb
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: 77ms
memory: 29384kb
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