QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#177915#6512. Completely Multiplicative Functionmendicillin2#RE 7ms8340kbC++172.4kb2023-09-13 15:52:012023-09-13 15:52:02

Judging History

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

  • [2023-09-13 15:52:02]
  • 评测
  • 测评结果:RE
  • 用时:7ms
  • 内存:8340kb
  • [2023-09-13 15:52:01]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }

template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;

using ll = int64_t;
using vi = vc<int>;

template <class F>
struct ycr {
	F f;
	
	template <class T>
	explicit ycr(T&& f_) : f(forward<T>(f_)) {}

	template <class... Args>
	decltype(auto) operator()(Args&&... args) {
		return f(ref(*this), forward<Args>(args)...);
	}
};
template <class F>
decltype(auto) yc(F&& f) {
	return ycr<decay_t<F>>(forward<F>(f));
}

const int MAXN = 1.1e6;
vi ps;
int pri[MAXN];

const int L = 30;
vector<int> prec[L+1][L+1];

void precomp() {
	fill(pri + 2, pri + MAXN, 0);
	for (int a = 2; a * a < MAXN; a++) {
		if (pri[a]) continue;
		for (int b = 2*a; b < MAXN; b += a) {
			if (!pri[b]) pri[b] = a;
		}
	}
	for (int a = 2; a < MAXN; a++) {
		if (pri[a] == 0) ps.push_back(a);
	}

	prec[1][1] = {1, 1};
	for (int n = 2; n <= L; n++) {
		vector<int> cur_ps;
		for (int p : ps) {
			if (p <= n) {
				cur_ps.push_back(p);
			} else {
				break;
			}
		}
		int num = int(cur_ps.size());
		for (int m = 0; m < (1 << num); m++) {
			vector<int> f(n+1, 0);
			f[1] = 1;
			for (int i = 0; i < num; i++) {
				int p = cur_ps[i];
				if (m & (1 << i)) {
					f[p] = 1;
				} else {
					f[p] = -1;
				}
			}
			int cur_k = 0;
			for (int a = 1; a <= n; a++) {
				if (f[a] == 0) {
					assert(pri[a] != 0);
					f[a] = f[a / pri[a]] * f[pri[a]];
					assert(abs(f[a]) == 1);
				}
				cur_k += f[a];
			}
			assert(abs(cur_k) <= n);
			if (cur_k >= 0) {
				prec[n][cur_k] = f;
			}
		}
	}
}

vector<int> solve(int N, int K) {
	if (N <= L) return prec[N][K];

	if ((N-K) % 2) return {};

	int need = (N-K) / 2;
	vector<int> res(N+1, 1);
	for (int p : ps) {
		if (p * p <= N) continue;
		if (p > N) break;
		int c = N/p;
		if (c <= need) {
			for (int a = p; a <= N; a += p) {
				res[a] = -1;
			}
			need -= c;
		}
	}
	assert(need == 0);
	return res;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	cout << fixed << setprecision(20);

	precomp();

	int T; cin >> T;
	while (T--) {
		int N, K; cin >> N >> K;
		auto res = solve(N, K);
		if (res.empty()) {
			cout << -1 << '\n';
		} else {
			assert(int(res.size()) == N+1);
			assert(accumulate(res.begin() + 1, res.end(), 0) == K);
			for (int i = 1; i <= N; i++) {
				assert(abs(res[i]) == 1);
				cout << res[i] << " \n"[i==N];
			}
		}
	}
}

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 8340kb

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
Runtime Error

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

result: