oj.uz

Submission #1077237

# Submission time Handle Problem Language Result Execution time Memory
1077237 2024-08-27T03:48:00 Z juicy Gondola (IOI14_gondola) C++17
100 / 100
 48 ms 6040 KB 
#include "gondola.h"

#include <bits/stdc++.h>

namespace {
  const int MD = 1e9 + 9;

  int p[250000], cur[100000];
  bool flg[250000], vis[100000];

  int bpow(int a, int b) {
    int res = 1;
    for (; b; a = (long long) a * a % MD, b /= 2) {
      if (b & 1) {
        res = (long long) res * a % MD;
      }
    }
    return res;
  }
}

int valid(int n, int *a) {
  std::map<int, bool> mp;
  for (int i = 0; i < n; ++i) {
    if (mp.count(a[i])) {
      return 0;
    }
    mp[a[i]] = 1;
    int x = a[i], y = a[(i + 1) % n];
    if (x <= n && y <= n) {
      --x, --y;
      if ((x + 1) % n != y) {
        return 0;
      }
    }
  }
  return 1;
}

int replacement(int n, int *a, int *res) {
  memset(p, -1, sizeof(p));
  memset(flg, 0, sizeof(flg));
  memset(vis, 0, sizeof(vis));
  auto fill = [&](int i, int x) {
    int cnt = 0;
    while (cnt++ < n) {
      p[x] = i;
      cur[i] = x + 1;
      i = (i + 1) % n;
      x = (x + 1) % n;
    }
  };
  for (int i = 0; i < n; ++i) {
    if (i == n - 1 || a[i] <= n) {
      fill(i, a[i] <= n ? a[i] - 1 : 0);
      break;
    }
  }
  int ma = 0;
  for (int i = 0; i < n; ++i) {
    p[a[i] - 1] = i;
    flg[a[i] - 1] = 1;
    ma = std::max(ma, a[i]);
  }
  int l = 0, j = 0;
  for (int i = 0; i < ma; ++i) {
    if (~p[i]) {
      if (i >= n) {
        res[l++] = cur[p[i]];
        cur[p[i]] = i + 1;
      }
      if (flg[i]) {
        vis[p[i]] = 1;
      }
    } else {
      while (vis[j]) {
        ++j;
      }
      res[l++] = cur[j];
      cur[j] = i + 1;
    }
  }
  return l;
}

int countReplacement(int n, int *a) {
  if (!valid(n, a)) {
    return 0;
  }
  int res = 1;
  std::sort(a, a + n);
  if (a[0] > n) {
    res = n;
  }
  int lst = n + 1, cnt = n;
  for (int i = 0; i < n; ++i) {
    if (a[i] > n) {
      res = (long long) res * bpow(cnt, a[i] - lst) % MD;
      lst = a[i] + 1;
    }
    --cnt;
  }
  return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 11 ms 2392 KB Output is correct
7 Correct 7 ms 1084 KB Output is correct
8 Correct 17 ms 4432 KB Output is correct
9 Correct 6 ms 1624 KB Output is correct
10 Correct 22 ms 4928 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 10 ms 2396 KB Output is correct
7 Correct 6 ms 1204 KB Output is correct
8 Correct 19 ms 4444 KB Output is correct
9 Correct 7 ms 1628 KB Output is correct
10 Correct 22 ms 4956 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 10 ms 1884 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 6 ms 1280 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1720 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1624 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1624 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1624 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1724 KB Output is correct
4 Correct 1 ms 1624 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1680 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 8 ms 2772 KB Output is correct
12 Correct 7 ms 2908 KB Output is correct
13 Correct 8 ms 2908 KB Output is correct
14 Correct 8 ms 2652 KB Output is correct
15 Correct 12 ms 3924 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 34 ms 4440 KB Output is correct
10 Correct 27 ms 3672 KB Output is correct
11 Correct 9 ms 1624 KB Output is correct
12 Correct 12 ms 1980 KB Output is correct
13 Correct 3 ms 604 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 33 ms 4432 KB Output is correct
10 Correct 30 ms 3864 KB Output is correct
11 Correct 9 ms 1624 KB Output is correct
12 Correct 12 ms 1884 KB Output is correct
13 Correct 3 ms 600 KB Output is correct
14 Correct 43 ms 5468 KB Output is correct
15 Correct 48 ms 6040 KB Output is correct
16 Correct 7 ms 1372 KB Output is correct
17 Correct 32 ms 4272 KB Output is correct
18 Correct 17 ms 2396 KB Output is correct