QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #209957 | #6512. Completely Multiplicative Function | ThinkofBlank | WA | 50ms | 21844kb | C++14 | 2.7kb | 2023-10-10 20:25:47 | 2023-10-10 20:25:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int f[N], g[N], p[N], e;
int ans[N], a[N][2], b[N];
bool ff[N];
bitset<201>dp[100];
inline void sai(){
g[1] = 1;
for(int i = 2; i < N; ++ i){
if(!f[i]){
p[++ e] = i; g[i] = i;
}
for(int j = 1; j <= e; ++ j){
if(i * p[j] >= N) break;
f[i * p[j]] = 1;
g[i * p[j]] = p[j];
if(i % p[j] == 0) break;
}
}
}
int main(){
sai(); srand(time(NULL));
int T;
scanf("%d", &T);
while(T --){
int n, k;
scanf("%d%d", &n, &k);
if((n + k) & 1) puts("-1");
else{
for(int i = 1; i <= n; ++ i) ans[i] = 1;
int tot = n - (n + k) / 2;//-1的个数
if(n >= 200){
int ed = sqrt(n);
for(int i = 1; i <= e; ++ i){
if(p[i] <= ed) continue;
if(p[i] > n) break;
int al = n / p[i];
if(tot >= al){
tot -= al;
for(int j = 1; j <= al; ++ j) ans[p[i] * j] = -1;
}
}
if(tot == 0){
for(int i = 1; i <= n; ++ i){
printf("%d ", ans[i]);
}
puts("");
}else puts("-1");
}else{
if(n == 1){
puts("1");
continue;
}
if(n == 2){
if(k == 0) puts("1 -1");
else puts("1 1");
continue;
}
if(n == 3){
if(k == 1) puts("1 1 -1");
else puts("1 1 1");
continue;
}
int ed = sqrt(n);
//对于小于等于ed的素数随机
int FF = 200; bool flag = 0; ff[1] = 1;
while(FF --){
for(int i = 2; i <= n; ++ i) ff[i] = 0;
int sv = tot, cnt = 0;
for(int i = 1; i <= e; ++ i){
if(p[i] > ed) break;
if(rand() & 1) ans[p[i]] = -1;
else ans[p[i]] = 1;
}
for(int i = 2; i <= n; ++ i){
if(g[i] <= ed) ff[i] = ff[i / g[i]];
if(ff[i]) ans[i] = (ans[i / g[i]] * ans[g[i]]), sv -= (ans[i] == -1);
}
if(sv < 0) continue;
for(int i = 1; i <= e; ++ i){
if(p[i] <= ed) continue;
if(p[i] > n) break;
int al = 0;
for(int j = p[i]; j <= n; j += p[i]){
al += (ans[j / p[i]] == 1);
}
++ cnt;
a[cnt][0] = al, a[cnt][1] = n / p[i] - al; b[cnt] = p[i];
}
dp[0].set(0);
for(int i = 1; i <= cnt; ++ i){
dp[i] = (dp[i - 1] << a[i][0]) | (dp[i - 1] << a[i][1]);
}
if(dp[cnt][sv]){
flag = 1;
for(int i = cnt; i; -- i){
if(sv >= a[i][0] && dp[i - 1][sv - a[i][0]]){
ans[b[i]] = -1, sv -= a[i][0];
}else{
ans[b[i]] = 1, sv -= a[i][1];
}
}
for(int i = 1; i <= n; ++ i){
ans[i] = ans[i / g[i]] * ans[g[i]];
printf("%d ", ans[i]);
}
puts("");
break;
}else continue;
}
if(!flag) puts("-1");
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 16528kb
input:
4 4 2 10 0 10 1 10 10
output:
1 1 -1 1 1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 1 1 1 1 1 1 1 1 1
result:
ok ok (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 50ms
memory: 21844kb
input:
11475 1 0 1 1 2 0 2 1 2 2 3 0 3 1 3 2 3 3 4 0 4 1 4 2 4 3 4 4 5 0 5 1 5 2 5 3 5 4 5 5 6 0 6 1 6 2 6 3 6 4 6 5 6 6 7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7 8 0 8 1 8 2 8 3 8 4 8 5 8 6 8 7 8 8 9 0 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 10 0 10 1 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10 11 0 11 1 11 2 11 3 11...
output:
-1 1 1 -1 -1 1 1 -1 1 1 -1 -1 1 1 1 1 -1 -1 1 -1 1 1 -1 1 -1 1 1 1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 1 -1 1 1 1 1 1 1 1 -1 1 -1 -1 -1 1 -1 -1 1 1 1 -1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1 1 -1 -1 -1 1 -1 -1 1 1 1 1 -1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 -1 -1 -1 1 1 -1 1 1 -1 ...
result:
wrong answer ans finds the answer, but out doesn't (test case 9853)