Submission #169191

#	Time	Username	Problem	Language	Result	Execution time	Memory
169191		DavidDamian	Gondola (IOI14_gondola)	C++11	75 / 100	61 ms	4724 KiB

gondola

#include "gondola.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
///Permutations
///Binary Exponentiation
///Determine wheather a sequence is a gondola sequence, a possible replacement sequence and the number of replacement sequences
map<int,int> used;
int valid(int n, int inputSeq[])
{
    int corresponding=1;
    int id_less_n=0;
    for(int i=0;i<n;i++){
        if(inputSeq[i]<=n){
            id_less_n=i;
            corresponding=inputSeq[i];
            break;
        }
    }
    for(int i=id_less_n;i<n+id_less_n;i++){
        if(used[ inputSeq[i%n] ]) return 0;
        used[ inputSeq[i%n] ]=1;
        if(inputSeq[i%n]>n){
            corresponding=(corresponding%n)+1;
            continue;
        }
        if(inputSeq[i%n]!=corresponding){
            return 0;
        }
        corresponding=(corresponding%n)+1;
    }
    return 1;
}

typedef pair<int,int> pii;
//First is equal to the actual gondola
//Second is equal to the original gondola
bool byActual(pii a,pii b)
{
    return a.first<b.first;
}
vector<pii> broken;
void getBrokenGondolas(int n,int gondolaSeq[]) ///Return a vector with broken gondolas in in increasing order
{
    int corresponding=1;
    int id_less_n=0;
    for(int i=0;i<n;i++){
        if(gondolaSeq[i]<=n){
            id_less_n=i;
            corresponding=gondolaSeq[i];
            break;
        }
    }
    for(int i=id_less_n;i<n+id_less_n;i++){
        if(gondolaSeq[i%n]>n) broken.push_back(pii(gondolaSeq[i%n],corresponding));
        corresponding=(corresponding%n)+1;
    }
    sort(broken.begin(),broken.end(),byActual);
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    getBrokenGondolas(n,gondolaSeq);
    int L=0;
    int act=n+1;
    for(pii x: broken){
        replacementSeq[L++]=x.second; //We add the original
        while(act<x.first){
            replacementSeq[L++]=act++; //Adds the intermediate gondolas
        }
        act++; //We update act since it is equal to the number of replaced gondola
    }
    return L;
}
typedef long long int ll;
ll mod=1000000009;
ll exponentiation(ll x,ll e)
{
    if(e==0) return (ll)1;
    if(e==1) return x;
    ll product=exponentiation(x,e/(ll)2);
    product=(product*product)%mod;
    if(e%2==1) product=(product*x)%mod;
    return product;
}
int countReplacement(int n, int inputSeq[])
{
    if(!valid(n,inputSeq)) return 0;
    ll total=1;
    getBrokenGondolas(n,inputSeq);
    ll act=n+1;
    ll N=broken.size();
    for(ll i=0;i<N;i++){
        ll x=broken[i].first;
        ll k=(ll)x-(ll)act; //This is the number of numbers that have N-i choices
        total=(total*exponentiation((ll)(N-i),k))%mod; //So we compute permutation with repetitions, of choices ((N-i)^k)
        act=x+1;
    }
    return total;
}

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