#include <bits/stdc++.h> #include "gondola.h" using namespace std; const int MOD = 1000000009; long long multiply(long long a, long long b) { long long ans = ((a % MOD) * (b%MOD)) % MOD; return ans; } long long exponentiate(long long a, long long b) { long long ans = a; for (int i = 0; i < b; i++) { ans = multiply(ans,b); } return ans; } int valid(int n, int inputSeq[]) { unordered_set<int> used; int current = -1; for (int i = 0; i < n; i++) { if (current==-1 && inputSeq[i] <= n) { current = inputSeq[i]; continue; } if (inputSeq[i] > n) { if (used.find(inputSeq[i])!=used.end()) { return 0; } used.insert(inputSeq[i]); current++; } if (inputSeq[i] <= n) { if (current==n && inputSeq[i] != 1) { return 0; } if (current!=n&&inputSeq[i] != current+1) { return 0; } current = inputSeq[i]; } } return 1; } int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int l =0; priority_queue<pair<int, int>,vector<pair<int,int>>, greater<pair<int,int>>> r; vector<int> original(n,-1); for (int i = 0; i < n; i++) { if (gondolaSeq[i] <= n) { int c = gondolaSeq[i]; for (int x = i; x < n; x++) { original[x] = c; if (c == n) { c = 1; } else { c++; } } c = gondolaSeq[i]; for (int x = (i-1); x >= 0; x--) { original[x]=c-1; if (c==1) { c = 5; } else{ c--; } } break; } if (i==(n-1)&&original[0]==-1) { for (int i = 0; i < n; i++) { original[i]=i+1; } } } for (int i = 0; i < n; i++) { if (gondolaSeq[i] > n) { r.push({gondolaSeq[i],original[i]}); } } int next = n+1; int arr_index = 0; while (!r.empty()) { int b = r.top().first; int o = r.top().second; r.pop(); replacementSeq[arr_index]=o; l++; next++; arr_index++; while (b>=next) { replacementSeq[arr_index] = next-1; l++; next++; arr_index++; } } return l; } int countReplacement(int n, int inputSeq[]) { if (valid(n,inputSeq)==0) { return 0; } long long p = 1; int next = n+1; vector<int> replaced; for (int i = 0; i < n; i++) { if (inputSeq[i] > n) { replaced.push_back(inputSeq[i]); } } sort(replaced.begin(),replaced.end()); if (replaced.size()==n) { p = multiply(p,n); } for (int i = 0; i < replaced.size()-1; i++) { if (next != replaced[i]) { long long num_options = replaced.size()-i; long long gap = replaced[i]-next; p = multiply(p,(exponentiate(num_options,gap))); next = replaced[i]+1; } } return p; } /*int main() { int s[4] = {1, 2, 7, 6}; cout << countReplacement(4,s) << endl; }*/