#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
bool check_valid(vector<ll>&stuff, ll n){
bool flag = true;
set<ll> cnt;
for (auto&i : stuff) cnt.insert(i);
if (cnt.size() != n) flag = 0;
ll mini = 10000000000;
ll pos = -1;
for (auto&i : stuff) mini = min(mini, i);
FOR(i,0,n) if (stuff[i] == mini)pos=i;
if (mini < n){
FOR(i,0,n){
if (stuff[pos%n] <=n && stuff[pos%n]!=mini) flag = 0;
pos++,mini++;
}
}
return flag;
}
vector<ll> repseq(vector<ll>&stuff, ll n){
vector<ll> should(n);
ll mini = 1000000000;
ll pos = -1;
for (auto&i : stuff) mini = min(mini, i);
FOR(i,0,n) if (stuff[i] == mini)pos=i;
if (mini > n) mini = 1, pos = 0;
FOR(i,0,n){
if (mini == n+1) mini = 1;
should[pos%n] = mini;
pos++,mini++;
}
vector<ll> ans;
vector<vector<ll>> shit;
FOR(i,0,n) shit.push_back({stuff[i], should[i]});
ll cur = n;
sort(shit.begin(), shit.end());
for (auto&i : shit){
while (cur < i[0]) ans.push_back(i[1]),i[1] = ++cur;
}
return ans;
}
ll binpow(ll a, ll b){
//cout << a << " " << b << endl;
if (b==0) return 1;
if (b%2==0) return (binpow(a,b/2)*binpow(a,b/2)) % 1000000009 ;
else return (binpow(a,b-1)*a)%1000000009;
}
ll numseq(vector<ll>&stuff, ll n){
vector<ll> should(n);
ll mini = 10000000000;
ll pos = -1;
vector<ll> shit;
vector<ll> lmfao;
ll cur = n;
ll ans = 1;
for (auto&i : stuff) if (i>n) shit.push_back(i);
ll idkman = shit.size();
sort(shit.begin(), shit.end());
for (auto&i : shit){
lmfao.push_back(i-cur-1);
cur = i;
}
for (auto&i : lmfao){
ans *= binpow(idkman, i);
idkman--;
ans %= 1000000009;
}
if(shit.size()==n) ans *= n, ans%=1000000009;
return ans;
}
int main(){
ll t;
cin >> t;
ll n; cin >> n;
vector<ll> stuff(n);
FOR(i,0,n) cin >> stuff[i];
if (!check_valid(stuff, n)) cout << 1;
else cout << numseq(stuff, n);
}
Compilation message
gondola.cpp: In function 'bool check_valid(std::vector<long long int>&, ll)':
gondola.cpp:15:17: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
15 | if (cnt.size() != n) flag = 0;
| ~~~~~~~~~~~^~~~
gondola.cpp: In function 'll numseq(std::vector<long long int>&, ll)':
gondola.cpp:88:16: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
88 | if(shit.size()==n) ans *= n, ans%=1000000009;
| ~~~~~~~~~~~^~~
gondola.cpp:68:5: warning: unused variable 'mini' [-Wunused-variable]
68 | ll mini = 10000000000;
| ^~~~
gondola.cpp:69:5: warning: unused variable 'pos' [-Wunused-variable]
69 | ll pos = -1;
| ^~~
/usr/bin/ld: /tmp/ccEHDXC4.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccNIciW6.o:gondola.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccEHDXC4.o: in function `main':
grader.cpp:(.text.startup+0xb6): undefined reference to `valid'
/usr/bin/ld: grader.cpp:(.text.startup+0x108): undefined reference to `countReplacement'
/usr/bin/ld: grader.cpp:(.text.startup+0x132): undefined reference to `replacement'
collect2: error: ld returned 1 exit status
