Submission #261335

#	Time	Username	Problem	Language	Result	Execution time	Memory
261335		A02	Gondola (IOI14_gondola)	C++14	100 / 100	84 ms	6520 KiB

gondola

#include "gondola.h"
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <utility>
#include <set>

using namespace std;

int valid(int n, int inputSeq[])
{

    vector<int> occurences (250001, 0);
    vector<int> index (n, -1);


    for (int i = 0; i < n; i++){
        occurences[inputSeq[i]]++;
        if (inputSeq[i] <= n){
            //cout << i << ' ' << reduced_sequence[i] << endl;
            index[inputSeq[i] - 1] = i;
        }
    }

    for (int i = 0; i < occurences.size(); i++){
        if (occurences[i] > 1){
            return 0;
        }
    }

    int lowest_g;
    for (int i = 0; i < n; i++){
        if (index[i] != -1){
            lowest_g = i;
            break;
        }
    }

    for (int i = lowest_g; i < n; i++){
        if (index[i] != -1){
            //cout << i << ' ' << index[i] << endl;
            if ((index[lowest_g] + i - lowest_g) % n != index[i]){
                return 0;
            }
        }
    }

    return 1;
}

int valid2(int n, int inputSeq[])
{

    vector<int> index (n, -1);
    set<int> occurences;

    for (int i = 0; i < n; i++){

        if (occurences.find(inputSeq[i]) != occurences.end()){
            return 0;
        }
        occurences.insert(inputSeq[i]);

        if (inputSeq[i] <= n){
            //cout << i << ' ' << reduced_sequence[i] << endl;
            index[inputSeq[i] - 1] = i;
        }
    }


    int lowest_g;
    for (int i = 0; i < n; i++){
        if (index[i] != -1){
            lowest_g = i;
            break;
        }
    }

    for (int i = lowest_g; i < n; i++){
        if (index[i] != -1){
            //cout << i << ' ' << index[i] << endl;
            if ((index[lowest_g] + i - lowest_g) % n != index[i]){
                return 0;
            }
        }
    }

    return 1;
}

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

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

    int first_original = 0;
    int first_value = 1;
    for (int i = 0; i < n; i++){
        if (gondolaSeq[i] <= n){
            first_original = i;
            first_value = gondolaSeq[i];
        }
    }

    vector<pair<int, int> > to_replace;

    for (int i = 0; i < n; i++){
        int current_pos = (i + first_original) % n;
        int current_original_value = (i + first_value);
        if (current_original_value > n){
            current_original_value -= n;
        }

        int target_value = gondolaSeq[current_pos];
        //cout << first_value << ' ' << i << ' ' << gondolaSeq[i] << endl;
        if (target_value != current_original_value){
            to_replace.push_back(make_pair(target_value, current_original_value));
        }
    }

    sort(to_replace.begin(), to_replace.end());

    int current_unused = n + 1;
    int current_replacement = 0;
    //cout << to_replace.size() << endl;
    for (int i = 0; i < to_replace.size(); i++){
        int c_value = to_replace[i].second;

        while (c_value != to_replace[i].first){
            replacementSeq[current_replacement] = c_value;
            c_value = current_unused;
            current_replacement++;
            current_unused++;
        }
    }

    return current_replacement;
}

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

long long fast_pow(long long a, long long k, long long p){

    if (k == 0){
        return 1;
    }

    if (a % p == 0){
        return 0;
    }

    if (k % 2 == 1){
        long long b = fast_pow(a, k / 2, p);
        return ((((b * b) % p) * a) % p);
    }

    long long b = fast_pow(a, k / 2, p);
    return ((b * b) % p);
}

int countReplacement(int n, int inputSeq[])
{

    long long p = 1000000009;

    if (valid2(n, inputSeq) == 0){
        return 0;
    }

    vector<long long> to_replace;

    to_replace.push_back(n);

    for (long long i = 0; i < n; i++){
        if(inputSeq[i] > n){
            to_replace.push_back(inputSeq[i]);
        }
    }

    sort(to_replace.begin(), to_replace.end());

    long long total = 1;

    long long current_options = to_replace.size() - 1;

    for (int i = 0; i < to_replace.size() - 1; i++){
        //cout << current_options << ' ' << to_replace[i + 1].first << ' ' << to_replace[i].first << endl;
        total *= fast_pow(current_options, (to_replace[i + 1] - to_replace[i] - 1), p);
        total %= p;

        current_options--;
    }

    long long N = n + 1;

    if (to_replace.size() == N){
        total *= N - 1;
        total %= p;
    }

    return ((int) total);
}

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:26:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < occurences.size(); i++){
                     ~~^~~~~~~~~~~~~~~~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:127:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < to_replace.size(); i++){
                     ~~^~~~~~~~~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:187:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < to_replace.size() - 1; i++){
                     ~~^~~~~~~~~~~~~~~~~~~~~~~
gondola.cpp:197:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (to_replace.size() == N){
         ~~~~~~~~~~~~~~~~~~^~~~
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:32:9: warning: 'lowest_g' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int lowest_g;
         ^~~~~~~~
gondola.cpp: In function 'int valid2(int, int*)':
gondola.cpp:72:9: warning: 'lowest_g' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int lowest_g;
         ^~~~~~~~

• 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