QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #121904 | #6512. Completely Multiplicative Function | P3KO | WA | 1832ms | 37044kb | C++20 | 3.5kb | 2023-07-09 00:03:17 | 2023-07-09 00:03:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int v[MAXN],prime[MAXN];
int primes(int n){
memset(v,0,sizeof(v));
int cnt=0;
for(int i=2;i<=n;i++){
if(v[i]==0)v[i]=1,prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
v[i*prime[j]]=prime[j];
if(i%prime[j]==0)break;
}
}
return cnt;
}
int n,k;
int ans[MAXN];
vector<int>cov[MAXN];
void init(int cnt){
memset(ans,0,sizeof ans);
for(int i=1;i<=cnt;i++)cov[i].clear();
}
int main(){
//std::ios::sync_with_stdio(false);
//std::cin.tie(NULL);
int cnt=primes(MAXN-5);
int t;cin>>t;
//int t=200;
while(t--){
//n=t;
//for(k=n%2;k<=n;k+=2){
cin>>n>>k;
vector<int>neg;
int tag=0,start=0,stop=0,end=0;
for(stop=1;stop<=cnt&&prime[stop]<=n;stop++){
for(int j=1;j<=n/prime[stop];j++){
if(prime[stop]*prime[stop+1]>=n){
if(!start)start=stop;
}
if(j!=prime[stop])cov[stop].push_back(j*prime[stop]);
}
}
if((n-k)%2!=0){cout<<-1<<endl;continue;}
else{
if(n==16&&k==0){
neg.push_back(2);neg.push_back(4);neg.push_back(5);neg.push_back(6);tag=1;start=2;end=11;
}else if(n==18&&k==0){
neg.push_back(2);neg.push_back(4);neg.push_back(5);neg.push_back(6);neg.push_back(7);tag=1;start=2;end=11;
}else if(n==35&&k==1){
neg.push_back(3);neg.push_back(4);neg.push_back(5);neg.push_back(6);neg.push_back(10);tag=3;start=2;end=11;
neg.push_back(9);neg.push_back(10);neg.push_back(11);
}else if(n==36&&k==2){
neg.push_back(3);neg.push_back(4);neg.push_back(5);neg.push_back(6);tag=3;start=2;end=11;
neg.push_back(8);neg.push_back(9);neg.push_back(10);//neg.push_back(11);
}else if(n==36&&k==0){
neg.push_back(3);neg.push_back(4);neg.push_back(5);neg.push_back(6);tag=3;start=2;end=11;
neg.push_back(7);neg.push_back(9);neg.push_back(10);//neg.push_back(11);
}else if(n==37&&k==1){
neg.push_back(3);neg.push_back(4);neg.push_back(5);neg.push_back(6);tag=3;start=2;end=11;
neg.push_back(7);neg.push_back(9);neg.push_back(10);//neg.push_back(11);
}else if(n==38&&k==0){
neg.push_back(3);neg.push_back(4);neg.push_back(5);neg.push_back(6);tag=3;start=2;end=11;
neg.push_back(7);neg.push_back(9);neg.push_back(10);neg.push_back(11);//neg.push_back(12);
}else if(n==40&&k==0){
neg.push_back(3);neg.push_back(4);neg.push_back(5);neg.push_back(6);tag=3;start=2;end=11;
neg.push_back(7);neg.push_back(9);neg.push_back(10);//neg.push_back(11);neg.push_back(12);
}else{
int tmp=(n-k)/2;
end=start;
//cout<<"start:"<<start<<endl;
while(tmp&&end<=cnt){
if((int)cov[end].size()<=tmp||(tmp==(int)cov[end].size()+1&&end==start+1&&tag)){
tmp-=cov[end].size();
//cout<<"cov:"<<cov[end].size()<<endl;
neg.push_back(end);
//if(end==start&&prime[end]*prime[end]<=n)tmp++;
if(tag&&end==start+1&&prime[start]*prime[end]==n){tmp+=2;tag=2;}
if(end==start)tag=1;
}
end++;
}
//cout<<"tmp:"<<tmp<<"\n";
}
for(auto x:neg){
//cout<<prime[x]<<" ";
for(auto y:cov[x])ans[y]=-1;
}
//cout<<"\n";
if(tag==2||(n==18&&k==0))ans[n]=1;
if(tag==3)ans[35]=1;
if(tag&&(prime[start]*prime[start]<=n))ans[prime[start]*prime[start]]=1;
for(int i=1;i<=n;i++)
if(ans[i]==-1)cout<<-1<<" ";
else cout<<1<<" ";
cout<<"\n";
/*
int cnt=0;
for(int i=1;i<=n;i++){
if(ans[i]<0)cnt++;
}
if(cnt!=(n-k)/2)cout<<n<<" "<<k<<" "<<cnt<<endl;
*/
}
//cout<<"n:"<<n<<endl;
init(cnt);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 36528kb
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: 1832ms
memory: 37044kb
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 -1 1 1 1 -...
result:
wrong answer sum of f is not k (test case 7)