Submission #1146243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146243		julia_08	Gondola (IOI14_gondola)	C++20	90 / 100	15 ms	2368 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAXN = 3e5 + 10;
const ll MOD = 1e9 + 9;

int marc[MAXN], num[MAXN];

int id(int x, int n){
  if(x == -1) return n - 1;
  if(x == n) return 0;
  return x;
}

int check_valid(int n, int inputSeq[]){

  for(int i=0; i<n; i++) marc[inputSeq[i]] = 0;

  for(int i=0; i<n; i++){
    marc[inputSeq[i]] ++;
    if(marc[inputSeq[i]] > 1) return 0;
  }

  int pos = n - 1;

  for(int i=0; i<n; i++){
    if(inputSeq[i] <= n){
      pos = min(pos, i);
    }
  }

  num[pos] = inputSeq[pos];

  int cur_num = inputSeq[pos] - 1;

  int cur_pos = id(pos - 1, n);

  while(cur_num > 0){
    num[cur_pos] = cur_num;
    cur_num --; cur_pos = id(cur_pos - 1, n);
  }

  cur_num = inputSeq[pos] + 1;

  cur_pos = id(pos + 1, n);

  while(cur_num <= n){
    num[cur_pos] = cur_num;
    cur_num ++; cur_pos = id(cur_pos + 1, n);
  }

  for(int i=0; i<n; i++){
    if(inputSeq[i] <= n && inputSeq[i] != num[i]){
      return 0;
    }
  }

  return 1;
}

int valid(int n, int inputSeq[]){
  return check_valid(n, inputSeq);
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]){

  int pos = n - 1;

  for(int i=0; i<n; i++){
    if(gondolaSeq[i] <= n){
      pos = min(pos, i);
    }
  }

  num[pos] = gondolaSeq[pos];

  int cur_num = gondolaSeq[pos] - 1;

  int cur_pos = id(pos - 1, n);

  while(cur_num > 0){
    num[cur_pos] = cur_num;
    cur_num --; cur_pos = id(cur_pos - 1, n);
  }

  cur_num = gondolaSeq[pos] + 1;

  cur_pos = id(pos + 1, n);

  while(cur_num <= n){
    num[cur_pos] = cur_num;
    cur_num ++; cur_pos = id(cur_pos + 1, n);
  }

  vector<pair<int, int>> v;

  for(int i=0; i<n; i++){
    if(gondolaSeq[i] > n){
      v.push_back({gondolaSeq[i], num[i]});
    }
  }

  sort(v.begin(), v.end());

  int l = 0;

  int cur = n + 1;

  for(auto [x, i] : v){

    replacementSeq[l ++] = i;

    while(cur != x){
      replacementSeq[l ++] = cur;
      cur ++;
    }

    cur ++; // x nao quebra
  }

  // for(int i=0; i<l; i++) cout << replacementSeq[i] << " ";

  // cout << "\n";

  return l;
}

ll exp(ll a, ll b){

  ll r = 1;

  for(int i=30; i>=0; i--){
    r = (r * r) % MOD;
    if(b & (1ll << i)) r = (r * a) % MOD;
  }

  return r;
}

int countReplacement(int n, int inputSeq[]){

  if(!check_valid(n, inputSeq)) return 0;

  vector<ll> v;

  for(int i=0; i<n; i++){
    if(inputSeq[i] > n){
      v.push_back((ll) inputSeq[i]);
    }
  }

  sort(v.begin(), v.end());

  ll ans = 1;

  ll last = n + 1;

  for(int i=0; i<(int) v.size(); i++){
    ans = (ans * exp(v.size() - i, v[i] - last)) % MOD;

    last = v[i] + 1;
  }

  // cout << ans << endl;

  bool ok = false;

  for(int i=0; i<n; i++){
    if(inputSeq[i] <= n){
      ok = true;
    }
  }

  if(!ok) ans = (ans * n) % MOD;

  return ans;
}

• 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: 0 / 10