Submission #866847

#	Time	Username	Problem	Language	Result	Execution time	Memory
866847		Onur_Ilgaz	Gondola (IOI14_gondola)	C++17	100 / 100	58 ms	6116 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define inf INT_MAX
#define ll long long
using namespace std;

int valid(int n, int arr[])
{
  int ind = 0, mn = inf;
  set <int> st;
  for(int i = 0; i < n; i++) {
    if(arr[i] < mn) ind = i, mn = arr[i];
    if(st.count(arr[i])) return 0;
    st.insert(arr[i]);
  }
  int now = mn + 1;
  // cout<<ind<<" "<<now<<" ";
  for(int i = (ind + 1) % n; i % n != ind; i = (i + 1) % n, now++) {
    if(arr[i] <= n and arr[i] != now) {
        return 0;
    }
  }
  return 1;
}

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

int replacement(int n, int arr[], int ans[])
{
  map <int, int> mp;
  int mxi = 0, mx = 0;
  int shift = 0;
  for(int i = 0; i < n; i++) {
    mp[arr[i]] = i;
    if(arr[i] > mx) mxi = i, mx = arr[i];
    if(arr[i] <= n) {
      shift = (arr[i] - i - 1) % n;
    }
  }
  int l = mx;
  mxi = (mxi + shift + n) % n + 1;
  for(int i = n + 1; i <= l; i++) {
    int val;
    if(mp.count(i)) {
      if(i == mx) val = mxi;
      else val = (mp[i] + shift + n) % n + 1;
    }
    else {
      val = mxi;
      mxi = i;
    }
    // cout<<val<<" "<<shift<<"\n";
    ans[i - (n + 1)] = val;
  }
  return l - n;
}

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

const int mod = 1000000009;

void duzelt(int n, int arr[]) {
  vector <int> brr(n);
  int ind = 0, mn = inf;
  for(int i = 0; i < n; i++) {
    if(arr[i] < mn and arr[i] <= n) ind = i, mn = arr[i];
  }
  if(mn == inf) mn = 1;
  ind = (ind - (mn - 1) + n) % n;
  int to = 0, i;
  for(i = (ind + 1) % n; i != ind; i = (i + 1) % n, to++) {
    brr[to] = arr[(i - 1 + n) % n];
  }
  brr[to] = arr[(i - 1 + n) % n];
  for(int i = 0; i < n; i++) arr[i] = brr[i];
}

int binpow(ll x, ll y) {
  ll ret = 1;
  while(y) {
    if(y & 1) {
       ret *= x;
       ret %= mod;
    }
    x *= x;
    x %= mod;
    y /= 2;
  }
  return ret;
}

int countReplacement(int n, int arr[])
{
    if(!valid(n, arr)) return 0;
    duzelt(n, arr);
    set <int> st;
    for(int i = 0; i < n; i++) {
      if(arr[i] > n) st.insert(arr[i]);
    }
    ll prev = n, len = st.size();
    bool is = len == n;
    ll ret = 1;
    for(auto till:st) {
      ll diff = till - prev - 1;
      ret *= binpow(len, diff);
      ret %= mod;
      prev = till;
      len--;
    }
    if(is) {
      ret *= n;
      ret %= mod;
    }
    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