Submission #1183466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183466		Albara_Abdulhafith	Gondola (IOI14_gondola)	C++20	55 / 100	32 ms	4680 KiB

gondola

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

  using namespace std;

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

  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[])
  {
    return -3;
  }

• 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