Submission #599468

#	Time	Username	Problem	Language	Result	Execution time	Memory
599468		AriaH	Gondola (IOI14_gondola)	C++17	100 / 100	72 ms	10072 KiB

gondola

#include "gondola.h"
#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 9;
const ll inf = 8e18;

ll pw(ll a, ll b)
{
  if(a == 0) return 0;
  ll ret = 1;
  while(b)
  {
    if(b & 1)
    {
      ret = ret * a % mod;
    }
    a = a * a % mod;
    b >>= 1;
  }
  return ret;
}

map < int, int > mark;

int valid(int n, int inputSeq[])
{
  int id = -1;
  for(int i = 0; i < n; i ++)
  {
    if(++ mark[inputSeq[i]] > 1) return 0;
    if(inputSeq[i] <= n)
    {
      id = i;
    }
  }
  if(id == -1) return 1;
  int start = (id - (inputSeq[id] - 1) + n + n) % n;
  for(int i = 0; i < n; i ++)
  {
    int j = (i + start) % n;
    if(inputSeq[j] > n) continue;
    if(inputSeq[j] != i + 1)
    {
      return 0;
    }
  }
  return 1;
}

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

int replacement(int n, int A[], int replacementSeq[])
{
  int Mx = 0;
  int id = -1;
  for(int i = 0; i < n; i ++)
  {
    Mx = max(Mx, A[i]);
    mark[A[i]] ++;
    if(A[i] <= n)
    {
      id = i;
    }
  }
  vector < int > vec;
  vec.push_back(Mx);
  for(int i = Mx - 1; i > n; i --)
  {
    if(mark[i] > 2) return -1;
    if(mark[i] == 0) vec.push_back(i);
  }
  int start;
  if(id == -1) { start = 0; }
  else { start = (id - (A[id] - 1) + n + n) % n; }
  for(int i = 0; i < n; i ++)
  {
    int j = (start + i) % n;
    if(A[j] <= n) continue;
    ///printf("i = %d j = %d\n", i, j);
    if(A[j] != Mx) replacementSeq[A[j] - n - 1] = i + 1;
    else
    {
      ///printf("here i = %d j = %d\n", i, j);
      int last = i + 1;
      while(SZ(vec))
      {
        int l = vec.back();
        ///printf("here l = %d last = %d\n", l, last);
        vec.pop_back();
        replacementSeq[l - n - 1] = last;
        last = l;
      }
    }
  }
  return Mx - n;
}

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

int countReplacement(int n, int A[])
{
  ll ret = 1;
  int id = -1;
  vector < int > vec;
  for(int i = 0; i < n; i ++)
  {
    mark[A[i]] ++;
    if(mark[A[i]] > 1) return 0;
    if(A[i] <= n)
    {
      id = i;
    }
    else
    {
      vec.push_back(A[i]);
    }
  }
  vec.push_back(n);
  sort(all(vec), greater < int > ());
  for(int i = 1; i < SZ(vec); i ++)
  {
    ret = ret * pw(i, vec[i - 1] - vec[i] - 1) % mod;
  }
  int start;
  if(id == -1)
  {
    ret = ret * n % mod;
    return ret;
  }
  else { start = (id - (A[id] - 1) + n + n) % n; }
  for(int i = 0; i < n; i ++)
  {
    int j = (start + i) % n;
    if(A[j] > n) continue;
    if(A[j] != i + 1) return 0;
  }
  return ret;
}

• 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