QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662664 | #1985. Decoration | AngelOlan | AC ✓ | 23ms | 35192kb | C++20 | 2.5kb | 2024-10-21 08:51:39 | 2024-10-21 08:51:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
vector<int> calc_div(int N) {
vector<int> div(N, 1);
vector<bool> is_prime(N, 1);
div[0] = 0;
for (int i = 2; i < N; ++i) {
if (!is_prime[i]) {
continue;
}
for (int j = i; j < N; j += i) {
is_prime[j] = 0;
int e = 0, aux = j;
while (aux % i == 0) {
++e;
aux /= i;
}
div[j] *= e + 1;
}
}
return div;
}
using i64 = long long;
constexpr i64 INF = 1e18;
signed main() {
cin.tie(0)->sync_with_stdio(0);
int N, K;
cin >> N >> K;
vector<int> div = calc_div(N), g(N), in_deg(N, 0);
for (int i = 0; i < N; ++i) {
g[i] = (i + div[i]) % N;
++in_deg[g[i]];
}
{
queue<int> q;
for (int i = 0; i < N; ++i) {
if (!in_deg[i]) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
--in_deg[g[u]];
if (!in_deg[g[u]]) {
q.push(g[u]);
}
}
}
vector<int> cycle_length(N);
for (int i = 0; i < N; ++i) {
if (!in_deg[i]) {
continue;
}
int v = g[i], length = 1;
while (v != i) {
++length;
v = g[v];
}
v = g[i];
cycle_length[i] = length;
while (v != i) {
in_deg[v] = 0;
cycle_length[v] = length;
v = g[v];
}
}
vector<vector<int>> jmp(25, vector<int>(N));
vector<vector<i64>> sum(25, vector<i64>(N));
for (int i = 0; i < N; ++i) {
jmp[0][i] = g[i];
sum[0][i] = i;
}
for (int i = 1; i < 25; ++i) {
for (int j = 0; j < N; ++j) {
jmp[i][j] = jmp[i - 1][jmp[i - 1][j]];
sum[i][j] = sum[i - 1][j] + sum[i - 1][jmp[i - 1][j]];
}
}
auto valid = [&](int u) -> bool {
int d = 0;
for (int i = 24; i >= 0; --i) {
if (!cycle_length[jmp[i][u]]) {
d += 1 << i;
u = jmp[i][u];
}
}
++d;
u = jmp[0][u];
return K - d <= cycle_length[u];
};
i64 ans = INF, node_ans;
for (int i = 0; i < N; ++i) {
if (!valid(i)) {
continue;
}
int u = i;
i64 curr = 0;
for (int j = 24; j >= 0; --j) {
if ((K >> j) & 1) {
curr += sum[j][u];
u = jmp[j][u];
}
}
if (curr < ans) {
ans = curr;
node_ans = i;
}
}
if (ans == INF) {
cout << -1 << '\n';
return 0;
}
for (int i = 0; i < K; ++i, node_ans = g[node_ans]) {
cout << node_ans << ' ';
}
cout << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 23ms
memory: 35192kb
input:
99999 30
output:
1 2 4 7 9 12 18 24 32 38 42 50 56 64 71 73 75 81 86 90 102 110 118 122 126 138 146 150 162 172
result:
ok correct
Test #2:
score: 0
Accepted
time: 21ms
memory: 35052kb
input:
99999 10
output:
1 2 4 7 9 12 18 24 32 38
result:
ok correct
Test #3:
score: 0
Accepted
time: 10ms
memory: 35036kb
input:
100000 9128
output:
55167 55183 55187 55195 55211 55219 55221 55229 55231 55235 55239 55243 55245 55261 55265 55273 55277 55281 55285 55289 55293 55301 55305 55317 55321 55327 55331 55333 55335 55367 55371 55375 55383 55387 55391 55399 55401 55409 55413 55425 55437 55445 55453 55457 55459 55463 55467 55473 55485 55505 ...
result:
ok correct
Test #4:
score: 0
Accepted
time: 20ms
memory: 35052kb
input:
100000 3000
output:
83 85 89 91 95 99 105 113 115 119 123 127 129 133 137 139 141 145 149 151 153 159 163 165 173 175 181 183 187 191 193 195 203 207 213 217 221 225 234 246 254 258 266 274 278 282 290 298 302 306 318 326 330 346 350 362 366 374 382 386 390 406 414 426 434 442 450 468 486 498 506 514 518 526 530 538 54...
result:
ok correct
Test #5:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
100 1
output:
0
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
1 1
output:
0
result:
ok correct
Test #7:
score: 0
Accepted
time: 16ms
memory: 35036kb
input:
100000 100000
output:
-1
result:
ok correct
Test #8:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
100 10
output:
1 2 4 7 9 12 18 24 32 38
result:
ok correct
Test #9:
score: 0
Accepted
time: 20ms
memory: 35052kb
input:
100000 6000
output:
83 85 89 91 95 99 105 113 115 119 123 127 129 133 137 139 141 145 149 151 153 159 163 165 173 175 181 183 187 191 193 195 203 207 213 217 221 225 234 246 254 258 266 274 278 282 290 298 302 306 318 326 330 346 350 362 366 374 382 386 390 406 414 426 434 442 450 468 486 498 506 514 518 526 530 538 54...
result:
ok correct
Test #10:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
101 19
output:
1 2 4 7 9 12 18 24 32 38 42 50 56 64 71 73 75 81 86
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
95 19
output:
60 72 84 1 2 4 7 9 12 18 24 32 38 42 50 56 64 71 73
result:
ok correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
95 22
output:
11 13 15 19 21 25 28 34 38 42 50 56 64 71 73 75 81 86 90 7 9 12
result:
ok correct
Test #13:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
92 5
output:
1 2 4 7 9
result:
ok correct
Test #14:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
92 6
output:
1 2 4 7 9 12
result:
ok correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
85 17
output:
40 48 58 62 66 74 78 1 2 4 7 9 12 18 24 32 38
result:
ok correct
Test #16:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
80 7
output:
1 2 4 7 9 12 18
result:
ok correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
8 4
output:
1 2 4 7
result:
ok correct