Submission #70348

#	Time	Username	Problem	Language	Result	Execution time	Memory
70348		alenam0161	Gondola (IOI14_gondola)	C++17	100 / 100	43 ms	3208 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int pos(int n,int rng[]){
    return min_element(rng,rng+n)-rng;
}
int ds(long long p,long long i,long long n){
    return i<p ? n-p+i:i-p;
}
int valid(int n, int inputSeq[])
{
  int mn=pos(n,inputSeq);
  int mx=inputSeq[mn];
  int se=mn;
  if(distance(inputSeq,unique(inputSeq,inputSeq+n))!=n)return 0;
  for(int j=1;j<n;++j){
      mn++;
      if(mn==n)mn=0;
      if(inputSeq[mn]<=n&&inputSeq[mn]-inputSeq[se]!=ds(se,mn,n)){
          return 0;
      }
      if(inputSeq[mn]<=n)mx=max(mx,inputSeq[mn]);
  }
  return 1;
}

//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{

  vector<pair<long long,long long>> vx;
  int p=pos(n,gondolaSeq);
  if(gondolaSeq[p]<=n){
    if(p-(gondolaSeq[p]-1)<0){
        p-=(gondolaSeq[p]-1);
        p=n+p;
    }
    else{
        p-=(gondolaSeq[p]-1);
    }
  }
  for(int i=0;i<n;++i){
        vx.push_back({gondolaSeq[i],ds(p,i,n)});
  }
  sort(vx.begin(),vx.end());
  int sz=0;
  for(auto to:vx){
    int x=to.first;
    int st=to.second+1;
    if(st!=x){
        replacementSeq[sz++]=st;
        while(true){
            n++;
            st=n;
            if(st<x)
            replacementSeq[sz++]=n;
            else break;
        }
    }
  //  cout<<x<< " "<<st<<endl;
  }
  return sz;
}
//----------------------
const long long mod = 1e9+9;
long long pmod(long long x,long long y){
    if(y==1)return x;
    if(y==0)return 1;
    long long k=pmod(x,y/2);
 //   cout<<k<<endl;
    k*=k;
    k%=mod;
 //   cout<<k<<endl;
    if(y%2==1)k*=x;
    k%=mod;
  //  cout<<k<<endl;
    return k;
}
int countReplacement(int n, int inputSeq[])
{
    if(valid(n,inputSeq)==0)return 0;
    long long p=pos(n,inputSeq);
    bool ok=true;
    if(inputSeq[p]<=n){
        ok=false;
        if(p-(inputSeq[p]-1)<0){
            p-=(inputSeq[p]-1);
            p=n+p;
        }
        else{
            p-=(inputSeq[p]-1);
        }//To Do
    }
    vector<pair<int,int>> vx;
     for(int i=0;i<n;++i){
        vx.push_back({inputSeq[i],ds(p,i,n)});
      }
    sort(vx.begin(),vx.end());
    int sz=0;
    long long ans=1;
    long long hw=n;
    long long m=n;
    for(auto to:vx){
        int x=to.first;
        int st=to.second+1;
     //   cout<<ans<<endl;
        if(st!=x){
          //  cout<<n<<" "<<x<<" << "<<hw<<endl;
            long long e=x-n-1;
            ans*=pmod(hw,e);
            ans%=mod;
            n=x;
        }
        hw--;
      //  cout<<x<< " "<<st<<endl;
    }
    if(ok)ans*=m;
    ans%=mod;
    return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:99:9: warning: unused variable 'sz' [-Wunused-variable]
     int sz=0;
         ^~

• 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