Submission #582236

#	Time	Username	Problem	Language	Result	Execution time	Memory
582236		Josia	Gondola (IOI14_gondola)	C++14	60 / 100	56 ms	5348 KiB

gondola

#include <bits/stdc++.h>

#include "gondola.h"


using namespace std;



const int mod = 1e9+9;


int valid(int n, int inputSeq[])
{
    deque<int> a(n);
    deque<int> perm(n);

    for (int i = 0; i<n; i++) {
        perm[i] = i;
        a[i] = inputSeq[i]-1;
    }

    for (int i=0; i<=n; i++) {
        if (a==perm) return 1;
        perm.push_back(perm[0]);
        perm.pop_front();
    }
    return 0;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int start = -1;
    for (int i = 0; i<n; i++) {
        gondolaSeq[i]--;
        if (gondolaSeq[i] < n) {
            if (start == -1)
                start = (n+i-gondolaSeq[i])%n;
            assert(start == (n+i-gondolaSeq[i])%n);
        }
    }
    if (start == -1) start = 0;

    set<pair<int, int>> replacements;

    set<int> okToReplace;

    for (int i = start; i<n+start; i++) {
        if (gondolaSeq[i%n] != i-start) {
            replacements.insert({gondolaSeq[i%n], i-start});
            okToReplace.insert(i-start);
        }
    }

    int curr = n;

    map<int, int> dict;

    for (int i: okToReplace) {
        dict[i]=i;
    }

    while (replacements.size()) {
        assert((*replacements.begin()).first >= curr);
        assert(okToReplace.size());
        if ((*replacements.begin()).first == curr) {
            replacementSeq[curr-n] = dict[(*replacements.begin()).second]+1;
            okToReplace.erase((*replacements.begin()).second);
            replacements.erase(replacements.begin());
        }

        else {
            replacementSeq[curr-n] = dict[*okToReplace.begin()]+1;
            dict[*okToReplace.begin()] = curr;
        }
        curr++;
    }
    return curr-n;
}

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

int countReplacement(int n, int inputSeq[])
{
    int start = -1;
    long int res = 1;
    for (int i = 0; i<n; i++) {
        inputSeq[i]--;
        if (inputSeq[i] < n) {
            if (start == -1)
                start = (n+i-inputSeq[i])%n;
            if (start != (n+i-inputSeq[i])%n) return 0;
        }
    }
    if (start == -1) {
        res = n;
        start = 0;
    }

    set<pair<int, int>> replacements;

    set<int> okToReplace;

    for (int i = start; i<n+start; i++) {
        if (inputSeq[i%n] != i-start) {
            replacements.insert({inputSeq[i%n], i-start});
            okToReplace.insert(i-start);
        }
    }

    int curr = n;

    while (replacements.size()) {
        if (!okToReplace.size()) return 0;
        if ((*replacements.begin()).first < curr) return 0;
        if ((*replacements.begin()).first == curr) {
            // replacementSeq[curr-n] = (*replacements.begin()).second+1;
            okToReplace.erase((*replacements.begin()).second);
            replacements.erase(replacements.begin());
        }

        else {
            // replacementSeq[curr-n] = *okToReplace.begin()+1;
            res *= okToReplace.size();
            res %= mod;
            okToReplace.erase(okToReplace.begin());
            okToReplace.insert(curr);
        }
        curr++;
    }

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