This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#ifndef hkoi
#include "gondola.h"
#endif
typedef long long ll;
void rotate(int n, int a[], int x){
int b[n];
for(int i = 0; i < n; i++){
b[i] = a[(i + n - x) % n];
}
for(int i = 0; i < n; i++){
a[i] = b[i];
}
}
bool init(int n, int a[]){
for(int i = 0; i < n; i++){
if(a[i] <= n){
rotate(n, a, a[i] - (i + 1));
break;
}
}
for(int i = 0; i < n; i++){
if(a[i] <= n && a[i] != i + 1){
return false;
}
}
set<int> S;
for(int i = 0; i < n; i++){
S.insert(a[i]);
}
if(S.size() != n){
return false;
}
return true;
}
int valid(int n, int a[]){
return init(n, a);
}
//----------------------
int replacement(int n, int a[], int r[]){
init(n, a);
int l = 0;
vector<int> seq;
for(int i = 0; i < n; i++){
seq.push_back(i + 1);
}
map<int, int> A; set<int> S;
for(int i = 0; i < n; i++)
A[a[i]] = i;
for(int i = 0; i < n; i++){
if(a[i] != i + 1){
S.insert(i);
}
}
int MAX_A = *max_element(a, a + n);
for(int i = n + 1; i <= MAX_A; i++){
if(!A.count(i)){
r[l++] = seq[*S.begin()];
seq[*S.begin()] = i;
}else{
r[l++] = seq[A[i]];
seq[A[i]] = i;
S.erase(A[i]);
}
}
return l;
}
//----------------------
const ll MOD = 1e9 + 9;
ll bp(ll a, ll b){
if(b == 0) return 1;
return bp(a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD;
}
ll mi(ll a){
return bp(a, MOD - 2);
}
ll C(ll n, ll r){
ll ret = 1;
for(ll i = n; i >= n - r + 1; i++){
ret = (ret * i) % MOD;
}
for(ll i = 1; i <= r; i++){
ret = (ret * mi(i)) % MOD;
}
}
int countReplacement(int n, int a[]){
bool ok = init(n, a);
if(!ok) return 0;
set<int> A; for(int i = 0; i < n; i++) A.insert(a[i]);
int MAX_A = *--A.end(), MIN_A = *A.begin();
ll FIXED = 0, _prev = n, ans = MIN_A > n ? n : 1;
for(auto a : A){
if(a > n){
ans = ans * bp(n - FIXED, a - _prev - 1) % MOD;
_prev = a;
}
FIXED++;
}
return ans;
}
#ifdef hkoi
int a[250001];
int b[250001];
int main() {
int ST;
cin >> ST;
int n; cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
if(1 <= ST && ST <= 3){
int ans = valid(n, a);
cout << ans << '\n';
}else if(4 <= ST && ST <= 6){
int l = replacement(n, a, b);
cout << l << '\n';
for(int i = 0; i < l; i++){
cout << b[i] << '\n';
}
}else if(7 <= ST && ST <= 10){
int ans = countReplacement(n, a);
cout << ans << '\n';
}
}
#endif
Compilation message (stderr)
gondola.cpp: In function 'bool init(int, int*)':
gondola.cpp:36:14: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
36 | if(S.size() != n){
| ~~~~~~~~~^~~~
gondola.cpp: In function 'll C(ll, ll)':
gondola.cpp:98:1: warning: no return statement in function returning non-void [-Wreturn-type]
98 | }
| ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:104:6: warning: unused variable 'MAX_A' [-Wunused-variable]
104 | int MAX_A = *--A.end(), MIN_A = *A.begin();
| ^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |