Submission #999209

#	Time	Username	Problem	Language	Result	Execution time	Memory
999209		Alfraganus	Gondola (IOI14_gondola)	C++17	75 / 100	33 ms	4996 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

int valid(int n, int a[]){
  vector<int> p;
  for(int i = 0; i < n; i ++){
    if(a[i] == 1){
      for(int j = i; j < n; j ++)
        p.push_back(a[j]);
      for(int j = 0; j < i; j ++)
        p.push_back(a[j]);
    }
  }
  if(p.size() == 0)
    return 0;
  for(int i = 0; i < n; i ++){
    if(p[i] != i + 1){
      return 0;
    }
  }
  return 1;
}

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

int replacement(int n, int a[], int replacementSeq[])
{
  int index = 0;
  for(int i = 0; i < n; i ++){
    if(a[i] <= n){
      index = (i - a[i] + 1 + n) % n;
      break;
    }
  }
  map<int, int> mp;
  int mx = 0;
  for(int i = index; i < n; i ++)
    if(a[i] > n)
      mp[a[i]] = i - index + 1, mx = max(mx, a[i]);
  for(int i = 0; i < index; i ++)
    if(a[i] > n)
      mp[a[i]] = i + n - index + 1, mx = max(mx, a[i]);
  if(mp.size() == 0)
    return 0;
  int ans = 0;
  for(int i = n + 1; i <= mx; i ++){
    if(mp.begin() -> first == i){
      replacementSeq[ans] = mp[i];
      mp.erase(mp.begin());
      ans ++;
    }
    else{
      replacementSeq[ans] = mp.begin() -> second;
      mp.begin() -> second = i;
      ans ++;
    }
  }
  return ans;
}

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

int countReplacement(int n, int a[]){
  map<int, int> cnt;
  for(int i = 0; i < n; i ++){
    cnt[a[i]] ++;
    if(cnt[a[i]] == 2)
      return 0;
  }
  int index = 0;
  for(int i = 0; i < n; i ++){
    if(a[i] <= n){
      index = (i - a[i] + 1 + n) % n;
      break;
    }
  }
  for(int i = index; i < n; i ++){
    if(a[i] <= n and a[i] != i - index + 1){
      return 0;
    }
  }
  for(int i = 0; i < index; i ++){
    if(a[i] <= n and a[i] != i + n - index + 1){
      return 0;
    }
  }
  long long ans = 1, mod = 1e9 + 9;
  vector<int> p;
  for(int i = 0; i < n; i ++)
    if(a[i] > n)
      p.push_back(a[i]);
  sort(p.begin(), p.end(), greater<int> ());
  auto binpow = [&](long long a, int n){
    long long res = 1;
    while(n){
      if(n & 1)
        res = (res * a) % mod;
      a = (a * a) % mod;
      n >>= 1;
    }
    return res;
  };
  long long x = p.size();
  for(int i = p.size() - 1; i >= 0; i --){
    ans = (ans * binpow(x, p[i] - (i + 1 == p.size() ? n : p[i + 1]) - 1)) % mod;
    x --;
  }
  int res = ans;
  return res;
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:106:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     ans = (ans * binpow(x, p[i] - (i + 1 == p.size() ? n : p[i + 1]) - 1)) % mod;
      |                                    ~~~~~~^~~~~~~~~~~

• 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