Submission #339986

#	Time	Username	Problem	Language	Result	Execution time	Memory
339986		bigDuck	Gondola (IOI14_gondola)	C++14	60 / 100	52 ms	5624 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

int mod=((int)1e9)+9;


map<int, int> cnt_valid;
int valid(int n, int inputSeq[])
{
    vector<pii> v;
    for(int i=0; i<n; i++){
        if(cnt_valid[inputSeq[i]]>0 ){
            return 0;
        }
        cnt_valid[inputSeq[i] ]++;
        if(inputSeq[i]<=n){
            v.pb({inputSeq[i], i} ) ;
        }
    }
    int ls=0;
    for(int i=0; i<v.size(); i++){
        if(i>0){
            if(v[i].ft<v[i-1].ft){ls++;}
            if(  abs(v[i].ft-( (v[i-1].ft==n)?(0):(v[i-1].ft) ) )!=abs(v[i].sc-v[i-1].sc)  ){return 0;}
        }
        if(ls>1){
            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[])
{
  if(!valid(n, inputSeq)){
    return 0;
  }
  set<ll> s;
  for(int i=0; i<n; i++){
    if(inputSeq[i]<=n){
        return 1;
    }
    s.insert({inputSeq[i]});
  }

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

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=0; i<v.size(); i++){
      |                  ~^~~~~~~~~

• 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: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10