Submission #446815

#	Time	Username	Problem	Language	Result	Execution time	Memory
446815		Deepesson	Gondola (IOI14_gondola)	C++17	90 / 100	1089 ms	5636 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(ind==-1)ind=0;
    if(val>n){return true;}
    int imaginario[n];
    int count = inputSeq[ind];
    if(ind==-1)count=0;
    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];
  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];
  if(ind==-1){count=1;ind=0;}
  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[])
{
  if(!valid(n,inputSeq))return 0;
  int array[n];
  for(int i=0;i!=n;++i)
    array[i]=inputSeq[i];
  std::priority_queue<int,std::vector<int>,std::greater<int>> queue;
  int count=0;
  for(int i=0;i!=n;++i){
    if(array[i]>n){
        queue.push(array[i]);
        count++;
    }
  }
  int gondola = n+1;
  long long resp = 1;
  if(count==n)resp=n;
  const long long mod = 1e9+9;
  while(count){
     if(gondola==queue.top()){
        queue.pop();
        --count;
     }else
     resp = (resp*count)%mod;
     ++gondola;
  }

  return resp;
}

• 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