QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#197967 | #6512. Completely Multiplicative Function | DepletedPrism# | WA | 137ms | 55872kb | C++17 | 5.4kb | 2023-10-02 22:51:40 | 2023-10-02 22:51:40 |
Judging History
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];
vector<int> ans;
vector<int> pr;
int n,k;
// vector<int> dfsf;
void dfs(vector<int> &dfsf,int now){
if(now==pr.size()){
int sum=0;
for(int i=1;i<=n;i++){
sum+=dfsf[i];
}
if(sum==k){
ans=dfsf;
}
return ;
}
int p=pr[now];
for(auto s:bin[p]){
dfsf[s]=-dfsf[s];
}
dfs(dfsf,now+1);
for(auto s:bin[p]){
dfsf[s]=-dfsf[s];
}
dfs(dfsf,now+1);
}
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--){
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;
}
if(n<=50){
ans.clear();
pr.clear();
// vector<int> pr;
for(int i=1;i<=cnt;i++){
if(prime[i]<=n){
pr.push_back(prime[i]);
}
}
vector<int> dfsf(n+1,1);
dfs(dfsf,0);
if(!ans.empty()){
for(int i=1;i<=n;i++){
cout<<ans[i]<<space;
}
cout<<endl;
}else{
cout<<-1<<endl;
}
continue;
}
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);
}
}
for(int kk=n/2;kk>=prime[now+1];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;
}
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: 3ms
memory: 55872kb
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: 137ms
memory: 55260kb
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 1347)