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;
#include "gondola.h"
int valid(int n, int inputSeq[]) {
int k = 0;
for(int i = 0; i < n; i ++) {
if(inputSeq[k] > inputSeq[i]) {
k = i;
}
}
if(inputSeq[k] <= n) {
for(int i = 1; i <= n - inputSeq[k]; i ++) {
int j = (k + i) % n;
if(inputSeq[j] <= n && inputSeq[j] != inputSeq[k] + i) {
return 0;
}
}
for(int i = 1; i <= inputSeq[k] - 1; i ++) {
int j = (k - i + n) % n;
if(inputSeq[j] <= n && inputSeq[j] != inputSeq[k] - i) {
return 0;
}
}
}
sort(inputSeq, inputSeq + n);
for(int i = 0; i + 1 < n; i ++) {
if(inputSeq[i] == inputSeq[i + 1]) {
return 0;
}
}
return 1;
}
//----------------------
vector<int> bld(int n, int k, int gondolaSeq[]) {
vector<int> seq;
seq.push_back(gondolaSeq[k]);
for(int i = 1; i <= n - gondolaSeq[k]; i ++) {
int j = (k + i) % n;
seq.push_back(gondolaSeq[j]);
}
reverse(seq.begin(), seq.end());
for(int i = 1; i <= gondolaSeq[k] - 1; i ++) {
int j = (k - i + n) % n;
seq.push_back(gondolaSeq[j]);
}
reverse(seq.begin(), seq.end());
return seq;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int k = 0;
for(int i = 0; i < n; i ++) {
if(gondolaSeq[k] > gondolaSeq[i]) {
k = i;
}
}
int l = 0;
if(gondolaSeq[k] > n) {
vector<pair<int, int>> p;
for(int i = 0; i < n; i ++) {
p.push_back({gondolaSeq[i], i + 1});
}
sort(p.begin(), p.end());
int j = n + 1;
for(int i = 0; i < n; i ++) {
if(p[i].first > n) {
replacementSeq[l ++] = p[i].second;
}
for(; j < p[i].first; j ++) {
replacementSeq[l ++] = j;
}
if(j == p[i].first) j ++ ;
}
} else {
vector<int> seq = bld(n, k, gondolaSeq);
vector<pair<int, int>> p;
for(int i = 0; i < n; i ++) {
p.push_back({seq[i], i + 1});
}
sort(p.begin(), p.end());
int j = n + 1;
for(int i = 0; i < n; i ++) {
if(p[i].first > n) {
replacementSeq[l ++] = p[i].second;
}
for(; j < p[i].first; j ++) {
replacementSeq[l ++] = j;
}
if(j == p[i].first) j ++ ;
}
}
return l;
}
//----------------------
const int mod = 1000000009;
int binpow(int a, int b) {
if(!b) return 1;
if(b % 2 == 0) {
int x = binpow(a, b / 2);
return 1LL * x * x % mod;
}
return 1LL * binpow(a, b - 1) * a % mod;
}
int countReplacement(int n, int inputSeq[]) {
if(!valid(n, inputSeq)) return 0;
int k = 0;
for(int i = 0; i < n; i ++) {
if(inputSeq[k] > inputSeq[i]) {
k = i;
}
}
vector<int> seq;
for(int i = 0; i < n; i ++) {
if(inputSeq[i] > n) {
seq.push_back(inputSeq[i]);
}
}
sort(seq.begin(), seq.end());
int curr = n;
int total = 1;
if(inputSeq[k] > n) {
for(int i = 0; i < n; i ++) {
total = 1LL * total * (i + 1) % mod;
}
}
for(int i = 0; i < seq.size(); i ++) {
total = 1LL * total * binpow((seq.size() - i), seq[i] - 1 - curr) % mod;
curr = seq[i];
}
return total;
}
Compilation message (stderr)
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:164:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for(int i = 0; i < seq.size(); 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... |