QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #671805 | #6512. Completely Multiplicative Function | masterhuang | WA | 769ms | 17180kb | C++23 | 1.6kb | 2024-10-24 14:32:15 | 2024-10-24 14:32:16 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
mt19937 rnd(time(0));
const int N=1e6+5;
int T,n,k,pr[N/10],mx[N],f[N],tot;bool v[N];
struct node{int p,x;}a[N];
vector<int>g[205][205];
inline void init(int M)
{
for(int i=2;i<=M;i++)
{
if(!v[i]) pr[++pr[0]]=i,mx[i]=i;
for(int j=1;j<=pr[0]&&i*pr[j]<=M;j++)
{
v[i*pr[j]]=1;mx[i*pr[j]]=mx[i];
if(i%pr[j]==0) break;
}
}
}
inline int calc(int n)
{
f[1]=1;for(int i=2;i<=n;i++) if(i!=mx[i]) f[i]=f[i/mx[i]]*f[mx[i]];
int c=0;for(int i=1;i<=n;i++) c+=(f[i]==1);return c;
}
inline void Init(int M)
{
for(int n=1;n<=200;n++)
{
for(int T=1;T<=66*n;T++)
{
vector<int>g;
for(int i=1,p=2;p<=n;p=pr[++i]) f[p]=(rnd()&1)?1:-1;
int m=calc(n);
for(int i=1;i<=n;i++) g.push_back(f[i]);
::g[n][m]=g;
}
}
}
inline void print()
{
if(calc(n)!=k) assert(0);
for(int i=1;i<=n;i++) cout<<f[i]<<" ";cout<<"\n";
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;init(N-5);Init(200);
while(T--)
{
cin>>n>>k;
if((n^k)&1){cout<<"-1\n";continue;}
k=(n+k)/2;
if(n>200)
{
int w=1,s=n;for(;pr[w]*pr[w]<=n;w++) f[pr[w]]=1;tot=0;
for(int i=w;pr[i]<=n&&i<=pr[0];i++) a[++tot]={pr[i],n/pr[i]},s-=n/pr[i];
s=k-s;
while(1)
{
shuffle(a+1,a+1+tot,rnd);int S=0;
for(int i=1;i<=tot;i++)
{
auto [p,x]=a[i];
if(S+x<=s) S+=x,f[p]=1;
else f[p]=-1;
}
if(S==s){print();break;}
}
}
else{for(int i:g[n][k]) cout<<i<<" ";cout<<"\n";}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 760ms
memory: 17180kb
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: 769ms
memory: 16820kb
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 sum of f is not k (test case 464)