QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #368174 | #6512. Completely Multiplicative Function | HuLiangyu# | WA | 142ms | 17348kb | C++14 | 5.1kb | 2024-03-26 21:29:29 | 2024-03-26 21:29:30 |
Judging History
answer
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <random>
using namespace std;
const long long maxn = 1e6 + 10;
int maxp;
int dvd[maxn];
int dvd_[maxn];
int pr [maxn];
int sel[maxn];
double now();
int rd() {
static mt19937 t(time(0));
uniform_int_distribution<int> dis(0, 1);
return dis(t) * 2 - 1;
}
int main() {
for (int i = 0 ;i < maxn; ++ i) {
dvd[i] = 1;
}
maxp = 0;
for (long long i = 2; i < maxn; ++ i) {
if (dvd[i] == 1) {
for (long long j = i * i; j < maxn ; j += i) {
dvd[j] = i;
dvd_[j] = j / i;
}
pr[maxp] = i;
++maxp;
}
}
int t;
cin >> t;
while (t--) {
// cout << "++";
int n, k;
cin >> n >> k;
if ((n-k) % 2 == 1) {
cout << -1 << endl;
}
else {
// PREPARE:
// prime_cnt: prime > sqrt(n) count
// maxp_of_tell: prime <= sqrt(n) count
int prime_cnt = 0;
for (long long i = 2 ; i<= n; ++ i) {
if (dvd[i] == 1 && i * i > n) {
prime_cnt += n / i;
}
}
int maxp_of_tell = 0;
for (long long i = 2 ; i * i <= n; ++ i) {
if (dvd[i] == 1)
++ maxp_of_tell;
}
// double now() : return present time.
bool isSolved = false;
double time = 0;
double begin_time = now();
while (time <= n * 1.0 / 2.0e6) {
time = now() - begin_time;
// n/2e6 case share 1.0 seconds.
int res = 1;
sel[0] = 0;
sel[1] = 1;
int changed = 0;
for (int i = 2; i <= n; ++ i) {
if (dvd[i] == 1) {
if (changed < maxp_of_tell)
sel[i] = rd();
else
sel[i] = -1;
changed ++;
}
else {
sel[i] = sel[dvd[i]] * sel[dvd_[i]];
}
res += sel[i];
}
vector<int> sel_cum;
sel_cum.push_back(0);
sel_cum.push_back(1);
int last = 1;
int lb = 0;
int rb = 1;
for (long long i = 2; i * i <= n; ++ i) {
last += sel[i];
sel_cum.push_back(last);
// lb += min(0, last);
// rb += max(0, last);
}
// for (int i = 1 ; i <= n; ++ i) {
// cout << sel[i];
// if (i == n) cout << endl;
// else cout << ' ';
// }
// cout << res << " " << k << " " << lb << " " << rb << endl;
changed = 0;
// if (res + 2 * lb <= k && k <= res + 2 * rb) {
// if (res <= k && k <= res + 2 * prime_cnt) {
isSolved = true;
// vector<int> app;
stack<int> app;
int left = (k - res) / 2;
for (int i = 2; i <= n && left != 0 ; ++ i) {
if (dvd[i] == 1) {
if (changed >= maxp_of_tell) {
if (left > 0 && sel_cum[n/i] > 0) {
app.push(i);
left -= sel_cum[n/i];
}
if (left < 0 && sel_cum[n/i] < 0) {
app.push(i);
left -= sel_cum[n/i];
}
}
changed ++;
}
}
if (left != 0) {
isSolved = false;
continue;
}
while (!app.empty()) {
int gt = app.top();
// cout << gt << "|";
app.pop();
for (int i = gt; i <= n; i += gt) {
sel[i] = -sel[i];
}
}
int test_res = 0;
for (int i = 1 ; i <= n; ++ i) {
test_res += sel[i];
cout << sel[i];
// if (i == n) cout << " " << test_res << endl;
if (i == n) cout << endl;
else cout << ' ';
}
break;
// }
time = now() - begin_time;
};
if (!isSolved) {
cout << -1 << endl;
}
}
}
}
double now() {
return 1.0 * clock() / CLOCKS_PER_SEC;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 13892kb
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: 142ms
memory: 17348kb
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 -1 1 1 1 1...
result:
wrong answer ans finds the answer, but out doesn't (test case 129)