QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#662664#1985. DecorationAngelOlanAC ✓23ms35192kbC++202.5kb2024-10-21 08:51:392024-10-21 08:51:39

Judging History

你现在查看的是最新测评结果

  • [2024-10-21 08:51:39]
  • 评测
  • 测评结果:AC
  • 用时:23ms
  • 内存:35192kb
  • [2024-10-21 08:51:39]
  • 提交

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