This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// M
#include<bits/stdc++.h>
#include "gondola.h"
using namespace std;
const int N = 300005, Mod = 1e9 + 9;
int n, A[N];
int valid(int _n, int inputSeq[])
{
n = _n;
for (int i = 0; i < n; i ++)
A[i] = inputSeq[i] - 1;
int st = -1;
map < int , int > MP;
for (int i = 0; i < n; i ++)
{
if (MP[A[i]])
return 0;
MP[A[i]] = 1;
if (A[i] < n)
st = i;
}
if (st == -1)
return 1;
for (int i = 0; i < n; i ++)
if (A[i] < n)
{
if (i <= st && (A[i] + st - i) % n != A[st])
return 0;
if (i > st && (A[st] + i - st) % n != A[i])
return 0;
}
return 1;
}
int replacement(int _n, int gondolaSeq[], int replacementSeq[])
{
n = _n;
for (int i = 0; i < n; i ++)
A[i] = gondolaSeq[i] - 1;
int st = -1;
for (int i = 0; i < n; i ++)
if (A[i] < n)
st = (i - A[i] + n) % n;
vector < int > M(N, -1);
for (int i = 0; i < n; i ++)
M[A[i]] = i;
int ptr = N - 1, fre = N - 1;
vector < int > V;
while (ptr >= n)
{
while (M[ptr] == -1 && ptr >= n)
ptr --;
if (ptr < n)
break;
fre = min(fre, ptr - 1);
int nw = M[ptr]; ptr --;
while (M[fre] != -1 && fre >= n)
fre --;
if (fre < n && st != -1)
{
V.push_back((nw - st + n) % n);
continue;
}
M[fre] = nw;
V.push_back(fre);
}
reverse(V.begin(), V.end());
for (int i = 0; i < (int)V.size(); i ++)
replacementSeq[i] = V[i] + 1;
return ((int)V.size());
}
int Power(int a, int b)
{
int ret = 1;
for (; b; b >>= 1, a = 1LL * a * a % Mod)
if (b & 1) ret = 1LL * ret * a % Mod;
return ret;
}
int countReplacement(int _n, int inputSeq[])
{
n = _n;
for (int i = 0; i < n; i ++)
A[i] = inputSeq[i];
if (!valid(n, A))
return 0;
vector < int > V;
for (int i = 0; i < n; i ++)
V.push_back(A[i]);
sort(V.begin(), V.end());
reverse(V.begin(), V.end());
bool ff = 0;
while ((int)V.size() && (int)V.back() < n)
V.pop_back(), ff = 1;
V.push_back(n - 1);
int tot = 1;
for (int i = 1; i < (int)V.size(); i ++)
tot = 1LL * tot * Power(i, V[i - 1] - V[i] - 1) % Mod;
if (!ff)
tot = 1LL * tot * n % Mod;
return tot;
}
# | 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... |