QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#500652 | #6728. To the Park | ssmy | WA | 42ms | 6256kb | C++20 | 2.2kb | 2024-08-01 17:14:34 | 2024-08-01 17:14:34 |
Judging History
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