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>
#include "gondola.h"
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const int mod = 1e9 + 9;
int vc[N];
int valid(int n, int v[])
{
int poz = -1, val, i;
for (i = 0; i < n; i++)
if (v[i] <= n)
{
val = v[i];
poz = i;
break;
}
if (poz == -1)
{
sort(v, v + n);
for (i = 1; i < n; i++)
if (v[i] == v[i - 1])
return 0;
return 1;
}
for (i = poz + 1; i < n; i++)
{
if (n < v[i])
continue;
int x = val + i - poz;
if (x > n)
x -= n;
if (x != v[i])
return 0;
}
sort(v, v + n);
for (i = 1; i < n; i++)
if (v[i] == v[i - 1])
return 0;
return 1;
}
struct ura{
int orig, now;
};
ura a[N];
bool cmp(ura x, ura y)
{
return x.now < y.now;
}
int replacement(int n, int v[], int ans[])
{
int poz = -1, cnt = 0, l = 0, val, i;
for (i = 0; i < n; i++)
if (v[i] <= n)
{
val = v[i];
poz = i;
break;
}
if (poz == -1)
poz = 0, val = 1;
for (i = 0; i < n; i++)
{
if (v[i] <= n)
continue;
int x = val + i - poz;
if (x > n)
x -= n;
a[++cnt] = {x, v[i]};
}
int last = n + 1;
sort(a + 1, a + cnt + 1, cmp);
for (i = 1; i <= cnt; i++)
{
ans[l++] = a[i].orig;
while(last < a[i].now)
{
ans[l++] = last;
last++;
}
last++;
}
return l;
}
int inm (int x, int y)
{
ll p = x;
ll q = y;
return x * y % mod;
}
int rid(int b, int e)
{
int r = 1;
while(e)
{
if (e % 2)
r = inm(r, b);
inm(b, b);
e /= 2;
}
return r;
}
int countReplacement(int n, int v[])
{
if (!valid(n, v))
return 0;
int ok = 1, i;
for(i = 0; i < n && ok; i++)
if(v[i] <= n)
ok = 0;
sort(v, v + n);
vector <int> v2;
v2.push_back(n);
int poz = -1;
for(i = 0; i < n; i++)
if(v[i] > n)
{
if(poz == -1)
poz = n - i;
v2.push_back(v[i]);
}
int sol = 1;
for(i = 0; i < v2.size() - 1; i++)
{
sol = inm(sol, rid(poz, v2[i + 1] - v2[i] - 1));
poz--;
}
if(ok)
sol = inm(sol, n);
return sol;
}
Compilation message (stderr)
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:22:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
22 | if (v[i] == v[i - 1])
| ^~
gondola.cpp:24:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
24 | return 1;
| ^~~~~~
gondola.cpp: In function 'int inm(int, int)':
gondola.cpp:87:8: warning: unused variable 'p' [-Wunused-variable]
87 | ll p = x;
| ^
gondola.cpp:88:8: warning: unused variable 'q' [-Wunused-variable]
88 | ll q = y;
| ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:123:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for(i = 0; i < v2.size() - 1; i++)
| ~~^~~~~~~~~~~~~~~
# | 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... |