QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #184330 | #6512. Completely Multiplicative Function | CSU2023# | WA | 26ms | 15456kb | C++14 | 2.9kb | 2023-09-20 17:04:34 | 2023-09-20 17:04:34 |
Judging History
answer
#include <bits/stdc++.h>
using std::bitset;
using std::ios;
using std::cin;
using std::cout;
const int N = 2e6 + 5;
const int L = 45;
int low[N], pri[N], f[N], ans[L][L][L];
int pn, T_data, n, k; bool allow[L][L];
const int wrong[7] = {16, 18, 35, 36, 37, 38, 40};
inline void sieve(int lim)
{
low[1] = 1;
for (int i = 2; i <= lim; ++i)
{
if (!low[i])
{
pri[++pn] = i;
low[i] = i;
}
for (int j = 1; j <= pn && 1ll * pri[j] * i <= lim; ++j)
{
int k = pri[j] * i;
low[k] = pri[j];
if (low[i] == pri[j])
break ;
}
}
}
int main()
{
// freopen("L.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
sieve(2e6);
for (int s = 0; s < 7; ++s)
{
int n = wrong[s];
int st = 0;
for (int i = 1; i <= pn && pri[i] <= n; ++i)
st = i;
for (int i = 0; i < (1 << st); ++i)
{
for (int j = 1; j <= n; ++j)
f[j] = 1;
for (int j = 1; j <= st; ++j)
if (i >> j - 1 & 1)
{
for (int k = pri[j]; k <= n; k *= pri[j])
for (int r = k; r <= n; r += k)
f[r] *= (-1);
}
int cnt = 0;
for (int j = 1; i <= n; ++i)
cnt += f[j];
if (cnt >= 0)
{
allow[n][cnt] = true;
for (int j = 1; j <= n; ++j)
ans[n][cnt][j] = f[j];
}
}
}
cin >> T_data;
while (T_data--)
{
cin >> n >> k;
if ((n - k) & 1)
cout << "-1\n";
else if (n != 16 && n != 18 && n != 35 && n != 36 && n != 37 && n != 38 && n != 40)
{
for (int j = 1; j <= n; ++j)
f[j] = 1;
int t = (n - k) / 2, ans = 0;
for (int i = 1; i <= pn && pri[i] <= n; ++i)
if (pri[i] * pri[i + 1] > n)
{
int temp = (n / pri[i]) - (pri[i] * pri[i] <= n);
ans += temp;
if (t >= temp)
{
t -= temp;
for (int j = pri[i]; j <= n; j += pri[i])
if (j != pri[i] * pri[i])
f[j] = -1;
}
}
assert(t == 0);
for (int j = 1; j <= n; ++j)
cout << f[j] << ' ';
cout << '\n';
}
else if (allow[n][k])
{
for (int j = 1; j <= n; ++j)
cout << ans[n][k][j] << ' ';
cout << '\n';
}
else
cout << "-1\n" << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 15456kb
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: 26ms
memory: 14228kb
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:
wrong answer ans finds the answer, but out doesn't (test case 138)