Submission #1277280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277280		Johann	Gondola (IOI14_gondola)	C++20	55 / 100	12 ms	6100 KiB

gondola

#include "gondola.h"

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

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

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

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;
}

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

int countReplacement(int n, int inputSeq[])
{
  return -3;
}

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