Submission #445585

#	Time	Username	Problem	Language	Result	Execution time	Memory
445585		Christopher_Rdz	Gondola (IOI14_gondola)	C++14	90 / 100	22 ms	2164 KiB

gondola

#include "gondola.h"
#include <assert.h>
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

bool visited[250003];
int rotos[250003];
bool rangos[250003];

struct dato{
    int valor;
    int pos;
};

bool operator <(const dato &a, const dato &b){
    return a.valor < b.valor;
}

dato gon[250003];

int valid(int n, int inputSeq[])
{
    int index = 0, aux, valor = 1;
    for (int i = 0; i < n; i++){
        aux = inputSeq[i];
        if (aux <= n){
            index = i;
            valor = aux;
            break;
        }
    }
    for (int i = index; i < n + index; i++){
        if (visited[ inputSeq[i % n] ]) return 0;
        visited[ inputSeq[i % n] ] = true;
        if (inputSeq[i % n] > n){
            valor = (valor % n) + 1;
            continue;
        }
        if (inputSeq[i % n] != valor) return 0;
        valor = (valor % n) + 1;
    }
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int index = 0, aux, valor = 1, L = 0, g = n + 1;
    for (int i = 0; i < n; i++){
        aux = gondolaSeq[i];
        if (aux <= n){
            index = i;
            valor = aux;
            break;
        }
    }
    int posi = 0;
    for (int i = index; i < n + index; i++){
        aux = gondolaSeq[i % n];
        if (aux > n ){
            gon[posi].valor = aux;
            gon[posi].pos = valor;
            posi++;
        }
        valor = (valor % n) + 1;
    }
    sort (gon + 0, gon + posi);
    g = n + 1;
    for (int i = 0; i < posi; i++){
        if (gon[i].valor <= n) continue;
        replacementSeq[L] = gon[i].pos;
        L++;
        while (g < gon[i].valor){
            replacementSeq[L] = g;
            g++;
            L++;
        }
        g = gon[i].valor + 1;
    }
    return L;
}

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

int countReplacement(int n, int inputSeq[])
{
    long long res = 1, maxi = 0, r = 0;
    bool uwu = false;
    if (!valid(n, inputSeq)) return 0;
    for (int i = 0; i < n; i++){
        if (inputSeq[i] > n){
            r++;
            if (inputSeq[i] > maxi) maxi = inputSeq[i];
            rangos[inputSeq[i]] = true;
        }
    }
    if (r == n) uwu = true;
    if (r == 0) return 1;
    long long int mod = 1000000009;
    for (int i = n + 1; i <= maxi; i++){
        if (rangos[i]){
            r--;
        }else{
            res = res * r % mod;
        }
    }
    if (uwu){
        res = res * n % mod;
    }
    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: 0 / 10