Submission #340043

#	Time	Username	Problem	Language	Result	Execution time	Memory
340043		bigDuck	Gondola (IOI14_gondola)	C++14	100 / 100	36 ms	6124 KiB

gondola

#include "gondola.h"

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount

ll mod=((ll)1000000000)+9;


map<int, int> cnt_valid;
int valid(int n, int inputSeq[])
{
     int i,j;
  for(i=0;i<n;i++)if(inputSeq[i]<=n)break;
  if(i<n)for(j=0;j<n;j++)if(inputSeq[j]<=n&&(inputSeq[j]+i)%n!=(inputSeq[i]+j)%n)return 0;
  std::sort(inputSeq,inputSeq+n);
  for(i=1;i<n;i++)if(inputSeq[i-1]==inputSeq[i])return 0;
  return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int pt=0, crd=0;
    for(int i=0; i<n; i++){
        if(gondolaSeq[i]<=n){
            pt=gondolaSeq[i], crd=i; break;
        }
    }

    int initial[100010];

    if(pt==0){
        for(int i=0; i<n; i++){
            initial[i]=i+1;
        }
    }
    else{
        for(int i=crd-pt+1, cnt=1; cnt<=n; i++){
            i+=n;
            i%=n;
            initial[i]=cnt;
            cnt++;
        }
    }

    set<pii> s;
    for(int i=0; i<n; i++){
        if(gondolaSeq[i]>n){
            s.insert({gondolaSeq[i], i} );
        }
    }

    if(s.empty()){
        return 0;
    }
    int cnt=n+1;
    for(auto it=s.begin(); it!=s.end(); it++){
        while(cnt<(it->ft) ){
            replacementSeq[cnt-n-1]=initial[it->sc]; initial[it->sc]=cnt; cnt++;
        }
        replacementSeq[cnt-n-1]=initial[it->sc]; initial[it->sc]=cnt;
        cnt++;
    }
    return cnt-1-n;
}

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


ll exp(ll x, ll e){

if(e==0){
    return 1;
}
if(e==1){
    return x%mod;
}
return (exp(x, e%2)*(exp( (x*x)%mod, e/2) ) )%mod ;

}



int countReplacement(int n, int inputSeq[])
{
    ll p=n;
  if(valid(n, inputSeq)==0){
    return 0;
  }
  multiset<ll> s;
  for(int i=0; i<n; i++){
    if(inputSeq[i]>n){s.insert({inputSeq[i]});}
    else{
        p--;
    }
  }


  ll ac=n+1;
  ll res=1;
  if( p==n ){
        res=n;
  }
    for(auto it=s.begin(); it!=s.end(); it++){
        res=(res*( exp(p, ((*it)-1)-ac+1 ) ) )%mod; ac=(*it)+1; p--;
    }
    return res;
}

• 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