IOI '14 P4 - Gondola (Standard I/O)

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

const int BASE = 1e9 + 9;
int add(int x, int y) {
    x += y;
    if (x >= BASE) return x-BASE;
    return x;
}
int mult(int x, int y) {
    return (long long)x*y % BASE;
}
int bin_pow(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1) res = mult(res, x);
        y >>= 1;
        x = mult(x, x);
    }
    return res;
}

bool valid(int n, const vector<int> &a) {
    int dif = -1;
    set<int> seen;
    for (int i = 0; i < n; ++i) {
        if (a[i] <= n) {
            int curDif = (a[i] - i + n) % n;
            if (dif == -1) dif = curDif;
            else if (dif != curDif) return false;
        }
        if (seen.count(a[i])) return false;
        seen.insert(a[i]);
    }
    return true;
}
vector<int> replacement(int n, const vector<int> &a) {
    int dif = 1, mx = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] <= n) dif = (a[i] - i + n) % n;
        if (a[i] > a[mx]) mx = i;
    }
    vector<int> b(n); // current array
    for (int i = 0; i < n; ++i) b[i] = (dif + i + n-1) % n + 1;

    vector<int> pos(1+a[mx], -1);
    for (int i = 0; i < n; ++i) pos[a[i]] = i;

    vector<int> replace;
    for (int i = n+1; i <= a[mx]; ++i) {
        if (pos[i] == -1) replace.push_back(b[mx]), b[mx] = i;
        else replace.push_back(b[pos[i]]), b[pos[i]] = i;
    }
    return replace;
}
int countReplacement(int n, const vector<int> &a) {
    if (!valid(n, a)) return 0;
    vector<int> b = a;
    sort(b.begin(), b.end());
    int ways = 1;
    for (int i = 0; i < n; ++i) {
        if (b[i] <= n) continue;
        int prev = (i ? b[i-1] : 0);
        int larger = n-i;
        // consider options for values between a[i] and a[i+1]
        int replacements = b[i]-1 - max(prev, n);
        ways = mult(ways, bin_pow(larger, replacements));
    }
    if (b[0] > n) ways = mult(ways, n);
    return ways;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T, n; cin >> T >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    if (1 <= T && T <= 3) { // check if gondola sequence
        cout << valid(n, a) << endl;
    } else if (4 <= T && T <= 6) { // find replacement sequence
        vector<int> v = replacement(n, a);
        cout << v.size();
        for (int x : v) cout << ' ' << x;
        cout << endl;
    } else { // 7 <= T && T <= 10, count replacement sequences
        cout << countReplacement(n, a) << endl;
    }
    return 0;
}