QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#197952#6512. Completely Multiplicative FunctionDepletedPrism#WA 46ms55680kbC++173.7kb2023-10-02 22:33:172023-10-02 22:33:17

Judging History

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

  • [2023-10-02 22:33:17]
  • 评测
  • 测评结果:WA
  • 用时:46ms
  • 内存:55680kb
  • [2023-10-02 22:33:17]
  • 提交

answer

/*
* @Author: zxxzy
* @Date:   2023-07-20 15:10:02
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <bitset>
#include <set>
#include <cmath>
#include <vector>
#include <map>
//#define int long long
#define space ' '
#define endl '\n'
#define de(x) cout<<"** "<<x<<" **"<<endl;
#define N 1000005
using namespace std;
using ll=long long;
const int mod=998244353;
const int INF=0x3f3f3f3f;
const double eps=1e-6;

int prime[N],vis[N],cnt=0;
void getmu(){
    for(int i=2;i<=N-5;i++){
        if(!vis[i]){
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt&&prime[j]*i<=N-5;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
vector<int> vec[N];
vector<int> bin[N];
signed main(){
    #ifdef LOCAL
        freopen("D:\\code2023\\test\\input.txt", "r", stdin);
        freopen("D:\\code2023\\test\\output.txt", "w", stdout);
    #endif
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    getmu();
    int T;
    cin>>T;
    while(T--){
        int n,k;
        cin>>n>>k;
        if((n+k)%2!=0){
            cout<<-1<<endl;
            continue;
        }
        for(int i=1;i<=n;i++){
            vec[i].clear();
            bin[i].clear();
        }
        for(int i=2;i<=n;i++){
            if(!vis[i]){
                for(int j=i;j<=n;j+=i){
                    vec[j].push_back(i);
                }
            }
        }
        for(int i=2;i<=n;i++){
            vector<int> s;
            int now=i;
            for(auto t:vec[i]){
                int ccnt=0;
                while(now%t==0){
                    ccnt++;
                    now/=t;
                }
                if(ccnt&1){
                    s.push_back(t);
                    bin[t].push_back(i);
                }
            }
            vec[i]=s;
        }
        vector<int> f(n+1);
        f[1]=1;
        for(int i=1;i<=n;i++){
            if(vec[i].size()%2==0){
                f[i]=1;
            }else{
                f[i]=-1;
            }
        }
        int sum=0;
        for(int i=1;i<=n;i++){
            sum+=f[i];
        }
        if(sum>k){
            cout<<-1<<endl;
            continue;
        }
        if(sum==k){
            for(int i=1;i<=n;i++){
                cout<<f[i]<<space;
            }
            cout<<endl;
            // de(3)
            continue;
        }
        int now=0;
        int flag=0;
        for(int kk=1;kk<=cnt;kk++){
            int tmp=0;
            for(auto s:bin[prime[kk]]){
                f[s]=-f[s];
                tmp+=f[s];
            }
            if(sum+2*tmp==k){
                for(int i=1;i<=n;i++){
                    cout<<f[i]<<space;
                }
                cout<<endl;
                flag=1;
                break;
            }
            if(sum+2*tmp>k){
                now=kk;
                for(auto s:bin[prime[kk]]){
                    f[s]=-f[s];
                    tmp+=f[s];
                }
                break;
            }
            sum+=2*tmp;
        }
        if(flag){
            continue;
        }
        vector<int> fre;
        for(int i=max(prime[now+1],n/2);i<=n;i++){
            if(!vis[i]&&vec[i].size()==1){
                fre.push_back(i);
            }
        }
        int need=(sum-k)/2;
        if(fre.size()<need){
            cout<<-1<<endl;
        }else{
            for(int i=0;i<need;i++){
                f[fre[i]]=-f[fre[i]];
            }
            for(int i=1;i<=n;i++){
                cout<<f[i]<<space;
            }
            cout<<endl;
        }
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 11ms
memory: 54772kb

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: 46ms
memory: 55680kb

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 23)