Submission #446810

#	Time	Username	Problem	Language	Result	Execution time	Memory
446810		Deepesson	Gondola (IOI14_gondola)	C++17	25 / 100	55 ms	4916 KiB

gondola

#include <bits/stdc++.h>
#include <gondola.h>
int valid(int n, int inputSeq[])
{
    std::map<int,bool> existe;
    for(int i = 0;i!=n;++i){
        auto&x=inputSeq[i];
        if(existe[x]){
            return false;
        }
        existe[x]=true;
    }
    int ind = -1;
    int val=1e6;
    for(int i=0;i!=n;++i){
        if(inputSeq[i]<=n){
            if(inputSeq[i]<val){
                val=inputSeq[i];
                ind=i;
            }
        }
    }
    if(val>n){return true;}
    int imaginario[n];
    int count = inputSeq[ind];
    for(int i=ind;i!=n;++i){
        imaginario[i]=count;
        ++count;
    }
    for(int i=0;i!=ind;++i){
        imaginario[i]=count;
        ++count;
    }
    for(int i=0;i!=n;++i) {
        if(inputSeq[i]>n)continue;
        if(inputSeq[i]!=imaginario[i]){return false;}
    }
    return true;

}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  int array[n];
  int padrao[n];
  for(int i=0;i!=n;++i)
    array[i]=gondolaSeq[i];
  std::map<int,int> vec;
  int max=0;
  for(int i=0;i!=n;++i){
    if(array[i]>n){
        vec[array[i]]=i;
        max=std::max(max,array[i]);
    }
  }
  if(!max)return 0;
  int cursor=0;
  int ind = -1;
  int val=1e6;
  for(int i=0;i!=n;++i){
    if(array[i]<=n){
        if(array[i]<val){
            val=array[i];
            ind=i;
        }
    }
  }
  int imaginario[n];
  int count = array[ind];
  for(int i=ind;i!=n;++i){
    imaginario[i]=count%(n);
    if(!imaginario[i])imaginario[i]=n;
    ++count;
  }
  for(int i=0;i!=ind;++i){
    imaginario[i]=count%(n);
    if(!imaginario[i])imaginario[i]=n;
    ++count;
  }
  for(;;){
    int proxima_gondola = cursor+n+1;
    auto it = vec.find(proxima_gondola);
    if(it==vec.end()){
        int subs = vec.begin()->second;
        replacementSeq[cursor]=imaginario[subs];
        imaginario[subs]=proxima_gondola;
    }else {
        int subs = it->second;
        replacementSeq[cursor]=imaginario[subs];
        imaginario[subs]=proxima_gondola;
        vec.erase(it);
    }
    ++cursor;
    if(!vec.size())break;
  }
  return cursor;
}

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

int countReplacement(int n, int inputSeq[])
{
  return -3;
}

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:47:7: warning: unused variable 'padrao' [-Wunused-variable]
   47 |   int padrao[n];
      |       ^~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10