Submission #1181363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181363		peteza	Gondola (IOI14_gondola)	C++20	75 / 100	13 ms	3144 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+9;

ll cpow(ll a, ll b) {
  ll res = 1;
  for(;b;b>>=1,a=a*a%mod) 
    if(b & 1) res = res*a % mod;
  return res;
}

int valid(int n, int inputSeq[]) {
  vector<int> tocheckunique(n);
  bool rotated = 0;
  for(int i=0;i<n;i++) tocheckunique[i] = inputSeq[i];
  for(int i=0;i<n;i++) {
    if(inputSeq[i] <= n) {
      rotated = 1;
      rotate(inputSeq, inputSeq+((i-(inputSeq[i]-1) < 0 ? n : 0) + i-(inputSeq[i]-1)), inputSeq+n);
      break;
    }
  }
  //cout << "bruh";
  sort(tocheckunique.begin(), tocheckunique.end());
  if(unique(tocheckunique.begin(), tocheckunique.end()) - tocheckunique.begin() != n) return 0;
  //rotate(inputSeq, inputSeq+1, inputSeq+n);
  if(!rotated) return 1;
  bool yes = 1;
  for(int i=0;i<n;i++) {
    if(inputSeq[i] <= n)
      yes &= (inputSeq[i] == i+1); 
  }
  return yes;
}

//----------------------
int cval[100005];
int bruhpos[250005];

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  if(!valid(n, gondolaSeq)) return -69420;
  //its valid but like just incaseor smth lol
  for(int i=0;i<n;i++) {cval[i] = i+1;}
  int ptr = 0;
  memset(bruhpos, -1, sizeof bruhpos);
  pair<int, int> bruhbruh(INT_MIN, -1);
  for(int i=0;i<n;i++) {
    if(gondolaSeq[i] > n) {
      bruhpos[gondolaSeq[i]] = i;
      bruhbruh = max(bruhbruh, {gondolaSeq[i], i});
    }
  }
  for(int i=n+1;i<=bruhbruh.first;i++) {
    if(bruhpos[i] == -1) {
      replacementSeq[ptr++] = cval[bruhbruh.second];
      cval[bruhbruh.second] = i;
    } else {
      replacementSeq[ptr++] = cval[bruhpos[i]];
      cval[bruhpos[i]] = i;
    }
  }
  return ptr;
}

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

int countReplacement(int n, int inputSeq[])
{
  if(!valid(n, inputSeq)) return 0;
  ll res = 1;
  vector<int> pospospos(1, n);
  for(int i=0;i<n;i++) {
    if(inputSeq[i] > n) {
      pospospos.push_back(inputSeq[i]);
    }
  }
  sort(pospospos.begin(), pospospos.end());
  for(int i=1;i<pospospos.size();i++) {
    res = (res * cpow(pospospos.size()-i, pospospos[i] - pospospos[i-1] - 1)) % 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: 0 / 15
• Subtask 10: 0 / 10