Submission #1183505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183505		Albara_Abdulhafith	곤돌라 (IOI14_gondola)	C++20	55 / 100	31 ms	4680 KiB

gondola

  #include "gondola.h"
  #include <map>
  #include <vector>
  #include <algorithm>

  using namespace std;

  typedef long long ll;

  const ll modu = ll(1e9) + 9ll;

  int mod(int x, int n){
    return ((x % n) + n) % n;
  }

  ll mod(ll x){
    return (x % modu);
  }

  ll fast(ll base, ll power){
    ll ret = 1ll;

    while(power){
      if(power & 1ll){
        ret = mod(ret * base);
      }

      power >>= 1;

      base = mod(base * base);
    }

    return ret;
  }

  int valid(int n, int inputSeq[])
  {
    int mn = n + 1;
    int id = -1;

    map<int, int> freq;

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

    if(id == -1){
      return 1;
    }

    for(int i = 0; i < n; i++){
      if(inputSeq[(i + id) % n] <= n and inputSeq[(i + id) % n] != mn){
        return 0;
      }
      mn++;
    }

    return 1;
  }

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

  int replacement(int n, int gondolaSeq[], int replacementSeq[])
  {
    int mn = n + 1;
    int id = -1;
    int not_used = n + 1;
    int l = 0;

    vector<pair<int, int>> v;

    for(int i = 0; i < n;i++){
      if(gondolaSeq[i] <= n and gondolaSeq[i] < mn){
        mn = gondolaSeq[i];
        id = i;
      }
      else if(gondolaSeq[i] > n){
        v.push_back(make_pair(gondolaSeq[i], i));
      }
    }

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

    if(id == -1){
      id = 0;
    }
    else{
      id = mod(id - mn + 1, n);
    }

    for(int i = 0; i < int(v.size()); i++){
      replacementSeq[l] = mod(v[i].second - id, n) + 1;
      l++;

      while(not_used < v[i].first){
        replacementSeq[l] = not_used;
        not_used++;
        l++;
      }
      not_used++;
    }

    return l;
  }

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

  int countReplacement(int n, int inputSeq[])
  {
    int mn = n + 1;
    int id = -1;

    map<int, int> freq;

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

    for(int i = 0; i < n and id != -1; i++){
      if(inputSeq[(i + id) % n] <= n and inputSeq[(i + id) % n] != mn){
        return 0;
      }
      mn++;
      if(mn > n){
        mn = 1;
      }
    }

    //============================================================

    ll ans = 1ll;

    bool check = true;
    ll not_used = ll(n) + 1ll;

    vector<ll> v;

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

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

    if(check){
      ans = mod(ans * ll(n));
    }

    ll sz = ll(v.size());
    for(ll i = 0ll; i + 1ll < sz; i++){
      ans = mod(ans * fast(sz - i, v[i] - not_used) );
      not_used = v[i] + 1ll;
    }

    return int(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: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10