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 "gondola.h"
#define pb push_back
#define mp(x...) array<int,2>({x})
#include <bits/stdc++.h>
using namespace std;
int n;
int *v;
int fix(int i)
{
int res = i % n;
if (res < 0)
res += n;
return res;
}
int right(int i)
{
return fix(i+1);
}
bool unique()
{
set<int> numbers;
for (int i = 0; i < n; i++)
{
if (numbers.find(v[i]) != numbers.end())
return 0;
numbers.insert(v[i]);
}
return 1;
}
int find_mi()
{
int mi = 0;
for (int i = 1; i < n; i++)
if (v[i] < v[mi])
mi = i;
return mi;
}
int valid(int nn, int vv[])
{
v = vv;
n = nn;
if (!unique())
return 0;
int mi = find_mi();
if (v[mi] > n)
return 1;
int si = fix(mi - v[mi] + 1);
if (v[si] != 1 && v[si] <= n)
return 0;
for (int j = right(si), i = 1; j != si; j=right(j))
if (v[j] != ++i && v[j] <= n)
return 0;
return 1;
}
//----------------------
int replacement(int nn, int vv[], int rr[])
{
n = nn;
v = vv;
int mi = find_mi();
vector<array<int, 2>> p;
int si = fix(mi - v[mi] + 1);
if (v[si] > n)
p.pb(mp(v[si], 1));
for (int j = right(si), i = 2; j != si; j=right(j), i++)
if (v[j] > n)
p.pb(mp(v[j], i));
sort(p.begin(), p.end());
int li = n;
for (auto [val, i] : p)
{
rr[(li++)-n] = i;
while (li != val) {rr[li-n] = li; li++;}
}
return li - n;
}
constexpr static int MOD = 1e9 + 9; // Kys :)
//----------------------
int mul(int64_t a, int64_t b)
{
int res = (a*b) % MOD;
if (res < 0)
res += MOD;
return res;
}
int pow(int a, int b)
{
int res = 1;
while (b)
{
if (b&1)
{
b--;
res = mul(res, a);
}
else
{
b >>= 1;
a = mul(a, a);
}
}
return res;
}
int countReplacement(int nn, int vv[])
{
n = nn;
v = vv;
int res = 1;
int mi = find_mi();
if (v[mi] > n)
res = n;
vector<int> vals;
if (!valid(n, v))
return 0;
for (int i = 0; i < n; i++)
if (v[i] > n)
vals.pb(v[i]);
sort(vals.begin(), vals.end());
int vs = vals.size();
int last = n;
for (int i : vals)
{
res = mul(res, pow(vs, i - last - 1));
last = i;
vs--;
}
return res;
}
# | 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... |