QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #445928 | #6512. Completely Multiplicative Function | Wavelet# | WA | 347ms | 7060kb | C++14 | 2.8kb | 2024-06-16 17:24:08 | 2024-06-16 17:24:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 3;
int W[MAXN]; bool P[MAXN];
int o = 1e6;
vector<int> M[100][100];
vector<int> solve(int n, int k){
vector <int> RES;
if(n <= 80){
// cout << "here" << endl;
if(!M[n][k].empty()){
RES = M[n][k];
} else {
RES.push_back(-1);
}
return RES;
}
for(int i = 1;i <= n;++ i)
W[i] = 1;
int m = floor(sqrt(n));
int w = n;
int tot = 0;
for(int i = m;i <= n;++ i) if(!P[i]){
int x = n / i;
if(i * i == n)
x = x - 1;
tot += x;
if(w - 2 * x >= k){
w -= 2 * x;
if(i * i == n){
for(int j = 1;1ll * i * j < n;++ j)
W[i * j] *= -1;
} else {
for(int j = 1;1ll * i * j <= n;++ j)
W[i * j] *= -1;
}
}
}
// cerr << "tot = " << tot << ", n = " << n << endl;
if(w == k){
for(int i = 1;i <= n;++ i)
RES.push_back(W[i]);
} else {
RES.push_back(-1);
}
return RES;
}
int main(){
// ios :: sync_with_stdio(false);
// cin.tie(nullptr);
for(int i = 2;i <= o;++ i){
for(int j = 2;1ll * i * j <= o;++ j)
P[i * j] = true;
}
W[1] = 1;
int m = 1 << 20;
for(int s = 0;s < m;++ s){
int sum = 1, cnt = 0;
for(int i = 2;i <= 80;++ i){
if(!P[i])
W[i] = (s & (1 << cnt)) ? -1 : 1, cnt ++;
else {
for(int j = 2;j < i;++ j){
if(i % j == 0){
W[i] = W[j] * W[i / j];
break;
}
}
}
sum += W[i];
if(sum >= 0 && M[i][sum].empty()){
vector <int> T;
for(int j = 1;j <= i;++ j)
T.push_back(W[j]);
M[i][sum] = T;
}
}
}
// for(int n = 2;n <= 80;++ n){
// for(int i = 1;i <= n;++ i)
// cout << M[n][i].empty() << " \n"[i == n];
// }
// for(int n = 2;n <= 500;++ n){
// for(int k = (n % 2 == 1 ? 1 : 0);k <= n;k += 2)
// assert(solve(n, k).size() > 1);
// }
int T;
cin >> T;
for(int _ = 1;_ <= T;++ _){
int n, k;
cin >> n >> k;
auto ANS = solve(n, k);
for(auto &u: ANS)
cout << u << " ";
cout << endl;
// cerr << "tot = " << tot << endl;
}
return 0;;
}
/*
1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 1 1 -1 -1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 292ms
memory: 6376kb
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: 347ms
memory: 7060kb
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...
result:
wrong answer ans finds the answer, but out doesn't (test case 2)