QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#129730 | #6512. Completely Multiplicative Function | Sorting# | TL | 71ms | 10420kb | C++ | 1.4kb | 2023-07-22 22:44:11 | 2023-07-22 22:44:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int iu=1e6;
bool isp[iu+1];
int pf[iu+1];
int pc;
int p[iu+1];
int n,k;
int ans[iu+1];
void solve(){
cin >> n >> k;
if(n%2!=k%2){
cout << "-1\n";
return;
}
k=(k+n)/2;
double cur=n;
int sz=0;
int bn=0;
for(int i=1; i<=pc ;i++){
if(p[i]>n) break;
sz=i;
if(p[i]*2>n) bn++;
}
for(int i=1; i<=n ;i++) ans[i]=1;
int gd=2;
while(true){
int sum=0;
for(int i=1; i<=n ;i++) sum+=ans[i];
//out << sum << endl;
if(sum-bn<=k){//success
for(int i=n/2+1; i<=n ;i++){
if(isp[i] && sum>k){
ans[i]=0;
sum--;
}
}
for(int i=1; i<=n ;i++) cout << ans[i]*2-1 << ' ';
cout << '\n';
return;
}
for(int i=gd; i<=n/2 ;i++){
if(!isp[i]) continue;
int cur=0;
for(ll z=i,s=1; z<=n ;z*=i,s*=-1){
for(int j=z; j<=n ;j+=z) cur+=(ans[j]*2-1)*s;
}
//cout << i << ' ' << cur << endl;
//system("pause");
if(sum-cur<k){
++gd;continue;
}
++gd;
for(ll z=i,s=1; z<=n ;z*=i,s*=-1){
for(int j=z; j<=n ;j+=z) ans[j]=1-ans[j];
}
break;
}
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
for(int i=2; i<=iu ;i++) isp[i]=true;
for(int i=2; i<=iu ;i++){
if(!isp[i]) continue;
p[++pc]=i;
for(int j=2*i; j<=iu ;j+=i){
isp[j]=false;
pf[j]=i;
}
}
int t;cin >> t;while(t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 15ms
memory: 10420kb
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: 0
Accepted
time: 36ms
memory: 10368kb
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:
ok ok (11475 test cases)
Test #3:
score: 0
Accepted
time: 44ms
memory: 10368kb
input:
8825 151 0 151 1 151 2 151 3 151 4 151 5 151 6 151 7 151 8 151 9 151 10 151 11 151 12 151 13 151 14 151 15 151 16 151 17 151 18 151 19 151 20 151 21 151 22 151 23 151 24 151 25 151 26 151 27 151 28 151 29 151 30 151 31 151 32 151 33 151 34 151 35 151 36 151 37 151 38 151 39 151 40 151 41 151 42 151 ...
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 ...
result:
ok ok (8825 test cases)
Test #4:
score: 0
Accepted
time: 71ms
memory: 10320kb
input:
5675 201 1 201 3 201 5 201 7 201 9 201 11 201 13 201 15 201 17 201 19 201 21 201 23 201 25 201 27 201 29 201 31 201 33 201 35 201 37 201 39 201 41 201 43 201 45 201 47 201 49 201 51 201 53 201 55 201 57 201 59 201 61 201 63 201 65 201 67 201 69 201 71 201 73 201 75 201 77 201 79 201 81 201 83 201 85...
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:
ok ok (5675 test cases)
Test #5:
score: 0
Accepted
time: 53ms
memory: 10412kb
input:
20000 100 15 90 62 96 81 98 52 93 86 91 60 96 50 96 71 96 85 97 88 94 72 100 76 98 75 93 81 100 93 98 13 96 47 96 25 100 21 94 46 100 75 90 66 91 89 100 33 98 73 92 61 96 57 97 11 97 92 98 49 90 11 100 21 99 32 99 48 96 87 90 15 99 67 99 14 94 90 94 30 94 56 93 66 98 16 99 52 90 63 95 3 97 53 100 58...
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 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1...
result:
ok ok (20000 test cases)
Test #6:
score: -100
Time Limit Exceeded
input:
2000 949 642 993 9 982 214 953 437 930 248 958 429 908 294 918 155 901 704 979 943 914 603 932 75 937 638 973 793 942 933 924 146 945 221 927 415 963 818 974 483 911 538 977 900 967 875 973 473 929 575 956 657 911 864 925 221 968 271 984 427 918 165 901 222 902 207 973 573 924 672 933 398 915 742 93...
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 ...