Submission #589069

#	Time	Username	Problem	Language	Result	Execution time	Memory
589069		Mamedov	Gondola (IOI14_gondola)	C++17	60 / 100	49 ms	4672 KiB

gondola

#pragma GCC optimize ("O3")
#include "gondola.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int valid(int n, int inputSeq[]) {
  set<int>s(inputSeq, inputSeq + n);
  if (size(s) < n) return 0;
  int shift = -1;
  for (int i = 0; i < n; ++i) {
    if (inputSeq[i] <= n) {
      if (shift == -1) shift = (inputSeq[i] - (i + 1) + n) % n;
      else if ((inputSeq[i] - (i + 1) + n) % n != shift) {
        return 0;
      }
    }
  }
  return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
  int shift = 0;
  vector<pii>rep;
  for (int i = 0; i < n; ++i) {
    if (gondolaSeq[i] <= n) {
      shift = (gondolaSeq[i] - (i + 1) + n) % n;
      break;
    }
  }
  for (int i = 0; i < n; ++i) {
    if (gondolaSeq[i] > n) {
      rep.eb(mpr(gondolaSeq[i], (i + shift) % n + 1));
    }
  }
  rep.eb(mpr(n, n));
  int ptr = 0;
  sort(all(rep), greater<pii>());
  int sz = size(rep);
  for (int i = 0; i < sz - 1; ++i) {
    for (int j = rep[i].f - 1; j > rep[i + 1].f; --j) {
      replacementSeq[ptr++] = j;
    }
    replacementSeq[ptr++] = rep[i].s;
  }
  reverse(replacementSeq, replacementSeq + ptr);
  return ptr;
}


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

const int mod = 1e9 + 9;
int binPow(int a, int n) {
  if (n == 0) return 1;
  if ((n & 1)) return (1ll * a * binPow(a, n - 1));
  else return binPow((1ll * a * a) % mod, n / 2);
}

int countReplacement(int n, int inputSeq[]) {
  if (!valid(n, inputSeq)) return 0;
  vector<int>rep;
  for (int i = 0; i < n; ++i) {
    if (inputSeq[i] > n) {
      rep.eb(inputSeq[i]);
    }
  }
  rep.eb(n);
  sort(all(rep), greater<int>());
  int sz = size(rep);
  int res = 1;
  for (int i = 1; i < sz; ++i) {
    res = (1ll * res * binPow(i, rep[i - 1] - rep[i] - 1)) % mod;
  }
  if (sz == n + 1) {
    res = (1ll * n * res) % 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: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10