Submission #802712

#	Time	Username	Problem	Language	Result	Execution time	Memory
802712		BERNARB01	Gondola (IOI14_gondola)	C++17	75 / 100	21 ms	2168 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"

using namespace std;

#ifdef B01
#include "../deb.h"
#else
#define deb(...)
#endif

const int md = 1000000009;

inline int mul(int a, int b) {
  a %= md;
  b %= md;
  return (int) ((long long) a * b % md);
}

int valid(int n, int p[]) {
  {
    vector<int> d(n);
    for (int i = 0; i < n; i++) {
      d[i] = p[i];
    }
    sort(d.begin(), d.end());
    d.resize(unique(d.begin(), d.end()) - d.begin());
    if ((int) d.size() != n) {
      return 0;
    }
  }
  vector<int> a(n);
  int s = (int) (min_element(p, p + n) - p);
  if (p[s] > n) {
    return 1;
  }
  for (int i = 0; i < n; i++) {
    a[(i + p[s] - 1) % n] = p[(s + i) % n];
  }
  vector<int> b;
  for (int i = 0; i < n; i++) {
    if (a[i] <= n && a[i] != i + 1) {
      return 0;
    }
  }
  return 1;
}

//----------------------

int replacement(int n, int p[], int res[]) {
  int mxi = (int) (max_element(p, p + n) - p);
  int m = p[mxi] - n;
  vector<int> a(n);
  int s = (int) (min_element(p, p + n) - p);
  if (p[s] <= n) {
    for (int i = 0; i < n; i++) {
      a[(i + p[s] - 1) % n] = p[(s + i) % n];
    }
  } else {
    for (int i = 0; i < n; i++) {
      a[i] = p[i];
    }
  }
  mxi = (int) (max_element(a.begin(), a.end()) - a.begin());
  vector<int> at(a[mxi] + 1, -1);
  for (int i = 0; i < n; i++) {
    if (a[i] > n) {
      at[a[i]] = i + 1;
    }
  }
  at[a[mxi]] = -1;
  mxi++;
  for (int i = 0; i < m; i++) {
    int v = n + i + 1;
    if (at[v] == -1) {
      res[i] = mxi;
      mxi = v;
    } else {
      res[i] = at[v];
    }
  }
  return m;
}

//----------------------

int countReplacement(int n, int p[]) {
  if (!valid(n, p)) {
    return 0;
  }
  int m = *max_element(p, p + n) - n;
  if (m == 0) {
    return 1;
  }
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    a[i] = p[i];
  }
  sort(a.begin(), a.end());
  int ans = 1;
  for (int i = 0; i < m; i++) {
    int v = n + i + 1;
    auto it = lower_bound(a.begin(), a.end(), v);
    if (*it == v) {
      continue;
    }
    assert(it == upper_bound(a.begin(), a.end(), v));
    ans = mul(ans % md, (int) (a.end() - it) % md);
  }
  return ans % md;
}

• 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: 0 / 15
• Subtask 10: 0 / 10