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"
#define MOD 1000000009
using namespace std;
int f[250010] , init[100010];
int valid(int n, int v[]){
int i , found , poz , ok , pin , fi , space;
found = -1;
poz = 0;
ok = 0;
for (i = 0 ; i < n ; i++)
v[i]--;
for (i = 0 ; i < n ; i++){
if (f[v[i]])
return 0;
f[v[i]] = 1;
if (v[i] < n){
if (found == -1){
found = v[i];
poz = i;
pin = i;
fi = v[i];
}
else {
if (found > v[i]){
if (ok == 1)
return 0;
ok = 1;
space = n - 1 - found + v[i];
if (space != i - poz - 1)
return 0;
found = v[i];
poz = i;
}
else {
space = v[i] - found - 1;
if (space != i - poz - 1)
return 0;
found = v[i];
poz = i;
}
}
}
}
/// verif cu ult poz si prima poz
if (found == -1)
return 1;
if (found > fi){
if (ok == 1)
return 0;
ok = 1;
space = n - 1 - found + fi;
if (space != (n - 1) - poz + pin)
return 0;
}
else {
if (!ok)
return 0;
space = fi - found - 1;
if (space != (n - 1) - poz + pin)
return 0;
}
return 1;
}
/// prima parte e ok
int replacement(int n, int v[], int w[]){
int found , maxi , p , i , len;
found = 0;
maxi = 0;
p = 0;
for (i = 0 ; i < n ; i++){
f[v[i]] = i + 1;
if (v[i] > maxi){
maxi = v[i];
p = i;
}
if (v[i] <= n){
found = v[i];
}
if (found){
init[i] = found;
found++;
if (found == n + 1)
found = 1;
}
}
if (!found) /// nu ai gasit pana acum, iei o secventa random
found = 1;
for (i = 0 ; i < n && init[i] == 0 ; i++){
init[i] = found;
found++;
if (found == n + 1)
found = 1;
}
len = 0;
for (i = n + 1 ; i <= maxi ; i++){
if (f[i]){ /// am nevoie de i
w[len] = init[ f[i] - 1 ];
init[f[i] - 1] = i;
}
else {
w[len] = init[p];
init[p] = i;
}
len++;
}
return len;
}
/// a doua parte e ok
int countReplacement(int n, int v[]){
int is_ok , found , maxi , i , places , poz , sol;
is_ok = valid (n , v);
if (!is_ok)
return 0;
found = 0;
maxi = 0;
for (i = 0 ; i < n ; i++){
v[i]++;
f[v[i]] = i + 1;
if (v[i] > maxi){
maxi = v[i];
}
if (v[i] <= n){
found = v[i];
}
if (found){
init[i] = found;
found++;
if (found == n + 1)
found = 1;
}
}
sort (v , v + n);
places = n;
poz = 0;
sol = 1;
for (i = 0 ; i < n && v[i] <= n ; i++){
places--;
poz++;
}
for (i = n + 1 ; i <= maxi ; i++){
if (v[poz] == i){
places--;
poz++;
}
else {
sol = (1LL * sol * places) % MOD;
}
}
return sol;
}
Compilation message (stderr)
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:81:15: warning: 'fi' may be used uninitialized in this function [-Wmaybe-uninitialized]
space = n - 1 - found + fi;
~~~~~~^~~~~~~~~~~~~~~~~~~~
gondola.cpp:95:36: warning: 'pin' may be used uninitialized in this function [-Wmaybe-uninitialized]
if (space != (n - 1) - poz + pin)
~~~~~~~~~~~~~~^~~~~
# | 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... |