QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#633535#9457. Prime Setucup-team4474#AC ✓98ms25304kbC++205.4kb2024-10-12 15:40:232024-10-13 18:38:38

Judging History

你现在查看的是测评时间为 2024-10-13 18:38:38 的历史记录

  • [2024-10-13 19:27:44]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果：AC
  • 用时：77ms
  • 内存：29384kb
查看
  • [2024-10-13 19:27:24]
  • hack成功，自动添加数据
  • (/hack/967)
  • [2024-10-13 18:38:38]
  • 管理员手动重测本题所有得分≥97分的提交记录
  • 测评结果：100
  • 用时：98ms
  • 内存：25304kb
查看
  • [2024-10-13 18:24:51]
  • hack成功，自动添加数据
  • (/hack/965)
  • [2024-10-13 18:17:54]
  • hack成功，自动添加数据
  • (/hack/963)
  • [2024-10-12 15:40:23]
  • 评测
  • 测评结果：100
  • 用时：85ms
  • 内存：27360kb
查看
  • [2024-10-12 15:40:23]
  • 提交

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';
    }
}
Source code, Language: C++20

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10ms
memory: 12444kb

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: 98ms
memory: 25304kb

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
English 繁體中文 简体中文

Server Time: 2024-11-30 00:33:18 | OpenSource Project