QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#231817 | #6512. Completely Multiplicative Function | ucup-team1198# | WA | 547ms | 17148kb | C++20 | 4.6kb | 2023-10-29 16:48:42 | 2023-10-29 16:48:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()
const int T = 18;
vector<int> prm;
const int MAXN = 1e6 + 100;
int mn[MAXN];
int64_t mlt[1 << T];
int ind[1 << T], sz[1 << T];
int val[1 << T];
int perfect_sqrt(int n) {
int res = sqrt(n);
while (res * res > n) --res;
while ((res + 1) * (res + 1) <= n) ++res;
return res;
}
int maxslow = 0;
map<array<int, 2>, vector<int>> mem;
void solve() {
int n, k;
cin >> n >> k;
/// n = abs(rand()) % 500 + 20, k = n % 2 + 2 * abs(rand()) % (min(n / 2, 10));
if ((n - k) % 2 != 0) {
cout << "-1\n";
return;
}
if (mem.count({n, k})) {
for (int x : mem[{n, k}]) {
cout << x << " ";
}
cout << "\n";
return;
}
int val = perfect_sqrt(n) + 1;
int lft = (n - k) / 2;
vector<int> ans;
for (int p : prm) {
if (p < val) continue;
if (p > n) break;
int x = (n / p);
if (lft >= x) {
lft -= x;
ans.push_back(p);
}
}
if (lft == 0) {
vector<int> out(n + 1, 1);
int id = 0;
for (int i = 2; i <= n; ++i) {
if (id < (int)ans.size() && i == ans[id]) {
out[i] = -1;
++id;
} else if (mn[i] == i) {
out[i] = 1;
} else {
out[i] = out[mn[i]] * out[i / mn[i]];
}
}
mem[{n, k}] = out;
for (int i = 1; i <= n; ++i) {
cout << out[i] << " ";
}
cout << "\n";
return;
}
/// cerr << "slow: " << n << " " << k << endl;
/// maxslow = max(maxslow, n);
/// cerr << maxslow << endl;
/**for (int mask = 0; mask < (1 << T); ++mask) {
val[mask] = 1;
if (sz[mask] % 2 == 1) {
val[mask] = -val[mask];
}
val[mask] *= perfect_sqrt(n / mlt[mask]);
}
for (int l = 1; l < (1 << T); l *= 2) {
for (int j = 0; j < (1 << T); j += 2 * l) {
for (int k = 0; k < l; ++k) {
val[j + k + l] += val[j + k];
}
}
}
for (int i = 0; i < (1 << T); ++i) {
if (val[i] == k) {
vector<int> ans;
for (int j = 0; j < T; ++j) {
if (i & (1 << j)) {
ans.push_back(prm[j]);
}
}
vector<int> out(n + 1, 1);
int id = 0;
for (int i = 2; i <= n; ++i) {
if (id < (int)ans.size() && i == ans[id]) {
out[i] = -1;
++id;
} else if (mn[i] == i) {
out[i] = 1;
} else {
out[i] = out[mn[i]] * out[i / mn[i]];
}
}
for (int i = 1; i <= n; ++i) {
cout << out[i] << " ";
}
cout << "\n";
return;
}
}*/
for (int mask = 0; mask < (1 << T); ++mask) {
vector<int> ans;
for (int j = 0; j < T; ++j) {
if (mask & (1 << j)) {
ans.push_back(prm[j]);
}
}
vector<int> out(n + 1, 1);
int id = 0;
int sum = 1;
for (int i = 2; i <= n; ++i) {
if (id < (int)ans.size() && i == ans[id]) {
out[i] = -1;
++id;
} else if (mn[i] == i) {
out[i] = 1;
} else {
out[i] = out[mn[i]] * out[i / mn[i]];
}
sum += out[i];
}
if (sum != k) continue;
mem[{n, k}] = out;
for (int i = 1; i <= n; ++i) {
cout << out[i] << " ";
}
cout << "\n";
return;
}
/// cerr << "bad!! " << n << " " << k << endl;
/// exit(0);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for (int i = 2; i < MAXN; ++i) {
if (mn[i] == 0) {
mn[i] = i;
prm.push_back(i);
}
for (int p : prm) {
if (p > i || i * p >= MAXN) break;
mn[i * p] = p;
}
}
mlt[0] = 1;
for (int i = 1; i < (1 << T); ++i) {
for (int j = 0; j < T; ++j) {
if (i & (1 << j)) {
ind[i] = j;
mlt[i] = mlt[i ^ (1 << j)] * prm[j];
sz[i] = sz[i ^ (1 << j)] + 1;
break;
}
}
}
int tst;
cin >> tst;
while (tst--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 10ms
memory: 12644kb
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: 0
Accepted
time: 47ms
memory: 14452kb
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 ...
result:
ok ok (11475 test cases)
Test #3:
score: 0
Accepted
time: 547ms
memory: 15308kb
input:
8825 151 0 151 1 151 2 151 3 151 4 151 5 151 6 151 7 151 8 151 9 151 10 151 11 151 12 151 13 151 14 151 15 151 16 151 17 151 18 151 19 151 20 151 21 151 22 151 23 151 24 151 25 151 26 151 27 151 28 151 29 151 30 151 31 151 32 151 33 151 34 151 35 151 36 151 37 151 38 151 39 151 40 151 41 151 42 151 ...
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...
result:
ok ok (8825 test cases)
Test #4:
score: 0
Accepted
time: 63ms
memory: 17148kb
input:
5675 201 1 201 3 201 5 201 7 201 9 201 11 201 13 201 15 201 17 201 19 201 21 201 23 201 25 201 27 201 29 201 31 201 33 201 35 201 37 201 39 201 41 201 43 201 45 201 47 201 49 201 51 201 53 201 55 201 57 201 59 201 61 201 63 201 65 201 67 201 69 201 71 201 73 201 75 201 77 201 79 201 81 201 83 201 85...
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:
ok ok (5675 test cases)
Test #5:
score: -100
Wrong Answer
time: 53ms
memory: 11876kb
input:
20000 100 15 90 62 96 81 98 52 93 86 91 60 96 50 96 71 96 85 97 88 94 72 100 76 98 75 93 81 100 93 98 13 96 47 96 25 100 21 94 46 100 75 90 66 91 89 100 33 98 73 92 61 96 57 97 11 97 92 98 49 90 11 100 21 99 32 99 48 96 87 90 15 99 67 99 14 94 90 94 30 94 56 93 66 98 16 99 52 90 63 95 3 97 53 100 58...
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 1 1 1 -1 1 1 1 1 -1 1...
result:
wrong answer f[12] != f[2] * f[6] (test case 59)