QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#810149	#6512. Completely Multiplicative Function	the_fool^#	WA	847ms	168552kb	C++20	2.8kb	2024-12-11 20:05:47	2024-12-11 20:05:48

Judging History

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

[2024-12-11 20:05:48]
评测

测评结果：WA
用时：847ms
内存：168552kb

查看

[2024-12-11 20:05:47]
提交

answer

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

using LL = long long;

constexpr int N = 1E6 + 10;

vector<int> prim;
int vis[N],m,f[N],k;

vector<vector<int> > prims;
vector<vector<int> > count_1;
int count_prime[N];
vector<int> px[40];

void solve() {
    int n,k;
    cin>>n>>k;
    if (1&(n^k)) {
        cout<<-1<<endl;
        return ;
    }
    int c_1 = n-(n+k)/2;
    int cp = count_prime[n] - count_prime[(n+1)/2];
    int id = -1;
    for (int i=0;i<40;i++) {
        if (count_1[i][n] + cp >= c_1 && count_1[i][n] <= c_1) {
            id = i;
        }
    }
    vector<int> res(n+1,1);
    for (int i=1;i<=n;i++) {
        if (count_1[id][i] - count_1[id][i-1])res[i] = -1;
    }
    int cntt = c_1 - count_1[id][n];
    int p = upper_bound(prim.begin(),prim.end(),n)-prim.begin()-1;
    while (prim[p]+prim[p]>n && cntt) {
        res[prim[p]] = -1;
        p--;
        cntt--;
    }
    for (int i=1;i<=n;i++) {
        cout<<res[i]<<' ';
    }
    cout<<endl;
    // int s = 0;
    // for (int i=1;i<=n;i++) {
    //     s += res[i];
    // }
    // assert(s == k);
    // cout<<"OK"<<endl;
}

#define lb(x) ((x)&-(x))
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);



    for (int i = 2; i < N; i++) {
        if (!vis[i]) {
            prim.emplace_back(i);
            for (int j = 2 * i; 1LL * j < N; j += i) {
                vis[j] = 1;
            }
        }
    }


    int _[] = {2,3,5,7,11};
    for (int i=0;i<32;i++) {
        int ii = i;
        prims.push_back({});
        while (ii) {
            prims.back().push_back(_[(int)log2(lb(ii))]);
            ii -= lb(ii);
        }
    }
    int __[] = {13,17,19,23,29,31,37,41};
    for (auto x: __) {
        prims.push_back({x});
    }
    count_1.resize(prims.size(),{0});
    vector<int> ___ = {2,3,5,7,11,13,17,19,23,29,31,37,41};
    for (int i=0;i<40;i++)px[i].push_back(0);
    m=prim.size();
    for (int i=1;i<=1e6;i++) {
        count_prime[i] = count_prime[i-1]+(vis[i]^1);
        vector<int> cnt;
        int ii = i;
        for (auto p : ___) {
            cnt.push_back(0);
            while (ii%p == 0) {
                cnt.back()++;
                ii/=p;
            }
        }
        for (int j=0;j<40;j++) {
            count_1[j].push_back(count_1[j].back());
            int xx = 0;
            if (j < 32) {
                int iii = j;
                while (iii) {
                    xx += cnt[(int)log2(lb(iii))];
                    iii-=lb(iii);
                }
            }
            else {
                xx = cnt[j-32+5];
            }
            count_1[j].back()+=xx&1;
        }
    }
    // cout<<k<<endl;
    int T;
    cin>>T;
    while (T--)solve();
}
/*
4
4 2
10 0
10 1
10 10
 */

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 838ms

memory: 167880kb

input:

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: 847ms

memory: 168552kb

input:

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:

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