Submission #1077237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077237		juicy	Gondola (IOI14_gondola)	C++17	100 / 100	48 ms	6040 KiB

gondola

#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10