QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#500652#6728. To the ParkssmyWA 42ms6256kbC++202.2kb2024-08-01 17:14:342024-08-01 17:14:34

Judging History

你现在查看的是最新测评结果

  • [2024-08-01 17:14:34]
  • 评测
  • 测评结果:WA
  • 用时:42ms
  • 内存:6256kb
  • [2024-08-01 17:14:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
// #define int long long
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int a[N];
bool st[N];
int cnt = 0;
bool vis[N];
vector <vector<int>> s(N);
void init(int n)
{
    st[0] = st[1] = 1;
    for(int i = 2; i <= n; i ++ )
    {
        if(!st[i]) 
        {
            a[++ cnt] = i;
        } 
        for(int j = 1; a[j] <= n / i; j ++ )
        {
            st[a[j] * i] = true;
            if(i % a[j] == 0)
            break;
        }
    }
}
void solve()
{
    int n;
    std:: cin >> n;
    int num = 0;
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i ++ )
    {
        s[i].clear();
        vis[i] = 0;
    }

    for(int i = 2; i <= n; i ++ )
    {
        cnt = 1;        
        if(!st[i])
        {
            for(int j = 2 * i; j <= n; j += i)
            {
                if(!vis[j])
                cnt ++ ;
            }

            if(cnt > 1)
            {
                num ++ ;
                vis[i] = 1;
                s[i].push_back(i);
                
                cnt -- ;
                if(cnt % 2 == 0)
                {
                    cnt -- ;
                }

                for(int j = 2 * i; j <= n && cnt; j += i)
                {
                    if(!vis[j])
                    {
                        num ++ ;
                        vis[j] = 1;
                        s[i].push_back(j);
                        cnt -- ;
                    }
                }
            }
        }
    }

    std:: cout << num / 2;
    for(int i = 2; i <= n; i ++ )
    {
        if(!st[i])
        {
            int len = s[i].size();
            for(int j = 0; j < len; j += 2)
            {
                std:: cout << " " << s[i][j] << " " << s[i][j + 1];
            }
        }
    }
    std:: cout << endl;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
    init(1e5 + 10);
    // for(int i = 1; i <= 1e5; i ++ )
    // {
    //     if(!st[i])
    //     {
    //         std:: cout << i << endl;
    //     }
    // }
    int T;
    std:: cin >> T;
    while(T -- )
	solve();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 5624kb

input:

3
1
4
6

output:

0
1 2 4
2 2 4 3 6

result:

ok 4 cases

Test #2:

score: -100
Wrong Answer
time: 42ms
memory: 6256kb

input:

1007
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101...

output:

0
0
0
1 2 4
1 2 4
2 2 4 3 6
2 2 4 3 6
2 2 4 6 8
3 2 4 6 8 3 9
4 2 4 6 8 3 9 5 10
4 2 4 6 8 3 9 5 10
4 2 4 6 8 10 12 3 9
4 2 4 6 8 10 12 3 9
5 2 4 6 8 10 12 3 9 7 14
6 2 4 6 8 10 12 3 9 5 15 7 14
6 2 4 6 8 10 12 14 16 3 9 5 15
6 2 4 6 8 10 12 14 16 3 9 5 15
6 2 4 6 8 10 12 14 16 3 9 15 18
6 2 4 6 8 1...

result:

wrong answer Case #18: Participant has a worse answer