QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209951#6512. Completely Multiplicative FunctionThinkofBlankWA 45ms20136kbC++142.7kb2023-10-10 20:21:132023-10-10 20:21:13

Judging History

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

  • [2023-10-10 20:21:13]
  • 评测
  • 测评结果:WA
  • 用时:45ms
  • 内存:20136kb
  • [2023-10-10 20:21:13]
  • 提交

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 = 100; 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[cnt][0] && dp[i - 1][sv - a[cnt][0]]){
								ans[b[i]] = -1, sv -= a[cnt][0];
							}else{
								ans[b[i]] = 1, sv -= a[cnt][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;
} 

详细

Test #1:

score: 100
Accepted
time: 9ms
memory: 20136kb

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: 45ms
memory: 19692kb

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 -1 1...

result:

wrong answer sum of f is not k (test case 21)