QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#184326#6512. Completely Multiplicative FunctionCSU2023#WA 31ms15412kbC++142.9kb2023-09-20 17:01:402023-09-20 17:01:41

Judging History

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

  • [2023-09-20 17:01:41]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:15412kb
  • [2023-09-20 17:01:40]
  • 提交

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];
            allow[n][cnt] = true;
            for (int j = 1; j <= n; ++j)
                ans[n][cnt][j] = f[j];
        }
    }
    cin >> T_data;
    // for (n = 1; n <= 1000000; ++n)
    while (T_data--)
    {
    //  k = n & 1;
        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;
                    }
                }
            if (t > 0)
                cout << "warning\n" << n << " " << t << '\n';
            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';
    }
}

详细

Test #1:

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

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: 31ms
memory: 15412kb

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)