| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 819941 | Cyber_Wolf | 곤돌라 (IOI14_gondola) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}