Submission #1277308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277308		Johann	Gondola (IOI14_gondola)	C++20	100 / 100	21 ms	6092 KiB

gondola

#include "gondola.h"

#include "bits/stdc++.h"
using namespace std;

#define sz(x) (int)(x.size())

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vi;
typedef vector<pii> vpii;

const ll MOD = 1e9 + 9;

void shift_inputSeq(int n, int inputSeq[], int shiftby)
{
  for (int i = 0; i < n; ++i)
    inputSeq[i] += shiftby;
}

int valid(int n, int inputSeq[])
{
  shift_inputSeq(n, inputSeq, -1);

  int shift2fix = -1;
  for (int i = 0; i < n; ++i)
  {
    if (inputSeq[i] < n)
    {
      int shift = (n + i - inputSeq[i]) % n;
      if (shift2fix == -1)
        shift2fix = shift;
      else if (shift2fix != shift)
        return 0;
    }
  }

  sort(inputSeq, inputSeq + n);
  for (int i = 0; i < n - 1; ++i)
    if (inputSeq[i] == inputSeq[i + 1])
      return 0;

  return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  shift_inputSeq(n, gondolaSeq, -1);

  int shift2fix = -1;
  for (int i = 0; i < n; ++i)
  {
    if (gondolaSeq[i] < n)
    {
      int shift = (n + i - gondolaSeq[i]) % n;
      if (shift2fix == -1)
        shift2fix = shift;
      else if (shift2fix != shift)
        assert(false);
    }
  }
  if (shift2fix == -1)
    shift2fix = 0;

  vpii replaced;
  for (int i = 0; i < n; ++i)
  {
    int idx = (shift2fix + i) % n;
    if (gondolaSeq[idx] != i)
    {
      assert(gondolaSeq[idx] > i);
      replaced.push_back({gondolaSeq[idx], i});
    }
  }

  sort(replaced.begin(), replaced.end());
  int m = n; // current gondola to place
  for (int i = 0; i < sz(replaced); ++i)
  {
    int to_replace = replaced[i].second;
    assert(m <= replaced[i].first);
    while (m <= replaced[i].first)
    {
      replacementSeq[m - n] = to_replace;
      to_replace = m;
      ++m;
    }
  }

  int final_size = m - n;
  shift_inputSeq(final_size, replacementSeq, +1);
  return final_size;
}

ll fastexp(ll base, ll exp)
{
  if (exp == 0)
    return 1;
  ll tmp = fastexp(base, exp / 2);
  ll res = (exp % 2 == 1) ? base : 1;
  res = (((res * tmp) % MOD) * tmp) % MOD;
  return res;
}
//----------------------
int foobar[100001];
int countReplacement(int n, int inputSeq[])
{
  copy(inputSeq, inputSeq + n, foobar);
  if (!valid(n, foobar))
    return 0; // needed because of multiple same numbers later...
  // return 1 if no gondola broke down

  shift_inputSeq(n, inputSeq, -1);

  int shift2fix = -1;
  for (int i = 0; i < n; ++i)
  {
    if (inputSeq[i] < n)
    {
      int shift = (n + i - inputSeq[i]) % n;
      if (shift2fix == -1)
        shift2fix = shift;
      else if (shift2fix != shift)
        assert(false);
    }
  }
  ll factor = 1;
  if (shift2fix == -1)
    shift2fix = 0, factor = n;

  vpii replaced;
  for (int i = 0; i < n; ++i)
  {
    int idx = (shift2fix + i) % n;
    if (inputSeq[idx] != i)
    {
      assert(inputSeq[idx] > i);
      replaced.push_back({inputSeq[idx], i});
    }
  }

  ll res = 1;
  sort(replaced.begin(), replaced.end());
  int m = n; // current gondola to place
  for (int i = 0; i < sz(replaced); ++i)
  {
    assert(m <= replaced[i].first);
    res = (res * fastexp(sz(replaced) - i, replaced[i].first - m)) % MOD;
    m = replaced[i].first + 1;
  }

  res = (res * factor) % MOD;
  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