#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
using namespace std;
using namespace __gnu_pbds;
#define lg long long
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const lg MOD = 1e9+9;
int valid(int n, int v[])
{
int idx = 0;
for(int i = 0; i < n; i++)
{
if(v[i] == 1) idx = i;
}
int x = n, b = 1, val = 1;
while(x--)
{
b &= (v[idx] == val);
idx = (idx+1)%n;
val++;
}
return b;
}
int replacement(int n, int v[], int r[])
{
int o = 0;
multiset<lg> mst, not_taken;
for(int i = 0; i < n; i++)
{
mst.insert(v[i]);
}
for(int i = 1; i <= *(--mst.end()); i++)
{
if(mst.find(i) == mst.end()) not_taken.insert(i);
}
while(not_taken.size())
{
int val = *(--mst.end());
mst.erase(--mst.end());
mst.insert(*(--not_taken.end()));
r[o++] = *(--not_taken.end());
not_taken.erase(--not_taken.end());
}
reverse(r, r+o);
return o;
}
lg fast_power(lg n, lg k)
{
lg ans = 1;
while(k)
{
if(k&1) ans = (ans*n)%MOD;
n = (n*n)%MOD;
k >>= 1;
}
return ans;
}
int countReplacement(int n, int in[])
{
int mxm = 0, un = 0;
set<lg> se;
for(int i = 0; i < n; i++)
{
mxm = max(mxm, in[i]);
un += (in[i] > n);
se.insert(in[i]);
}
if(se.size() < n) return 0;
int ans = 1;
for(lg i = 1; i <= mxm-n-un; i++) ans = (ans*i)%MOD;
for(lg i = 1; i < mxm-n; i++) ans = (ans*i)%MOD;
for(lg i = 1; i < un; i++) ans = (ans*fast_power(i, MOD-2))%MOD;
return ans;
}
int main()
{
fastio;
int tc;
cin >> tc;
while(tc--)
{
int n, t;
cin >> n >> t;
int v[n], lj[100];
memset(lj, 0, sizeof(lj));
for(int i = 0; i < n;i++) cin >> v[i];
if(t == 1)
{
cout << valid(n, v) << '\n';
}
else if(t == 2)
{
int an = replacement(n, v, lj);
cout << an << '\n';
}
else{
cout << countReplacement(n, v) << '\n';
}
}
return 0;
}
Compilation message
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:47:7: warning: unused variable 'val' [-Wunused-variable]
47 | int val = *(--mst.end());
| ^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:79:15: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
79 | if(se.size() < n) return 0;
| ~~~~~~~~~~^~~
/usr/bin/ld: /tmp/cc33yumL.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccK9w27J.o:gondola.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc33yumL.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
