Submission #446817

#	Time	Username	Problem	Language	Result	Execution time	Memory
446817		Deepesson	Gondola (IOI14_gondola)	C++17	100 / 100	77 ms	6380 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;

}

//----------------------
long long modpow(long long a,long long b){
    if(!b)return 1;
    const long long mod = 1e9+9;
    typedef std::pair<long long,long long> pll;
    std::vector<pll> vec;
    long long c = 1;
    long long val = a;
    vec.push_back({1,val});
    while(c<b){
        c*=2;
        val=(val*val)%mod;
        vec.push_back({c,val});
    }
    long long resp = 1;
    while(vec.size()){
        while(vec.back().first<=b){
            b-=vec.back().first;
            resp=(resp*vec.back().second)%mod;
        }
        vec.pop_back();
    }
    return resp;
}
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){
    int proximo = queue.top();
    int movs = proximo-gondola;
    long long x = modpow(count,movs);
    gondola=queue.top()+1;
    queue.pop();
    resp=(resp*x)%mod;
    --count;
  }
  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: 10 / 10