# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1025107 | nvujica | Gondola (IOI14_gondola) | C++14 | 19 ms | 2776 KiB |
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 ll long long
#define fi first
#define se second
using namespace std;
const int maxn = 3e5 + 10, mod = 1e9 + 9, LOG = 30;
int a[maxn];
int bio[maxn];
vector <pair<int, int> > v;
int pot[LOG];
int mul(int x, int y){
return ((ll)x * y) % mod;
}
int valid(int n, int inputSeq[]){
for(int i = 0; i < n; i++){
a[i] = inputSeq[i] - 1;
if(bio[a[i]]) return 0;
bio[a[i]] = 1;
}
for(int i = 0; i < n; i++){
if(a[i] < n){
for(int j = 0; j < n; j++){
if(a[(i + j) % n] < n){
if(a[(i + j) % n] != (a[i] + j) % n) return 0;
}
}
break;
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
for(int i = 0; i < n; i++){
a[i] = gondolaSeq[i];
}
for(int i = 0; i < n; i++){
if(a[i] > n) v.push_back({a[i], i});
}
for(int i = n - 1; i >= 0; i--){
if(a[i] <= n || !i){
for(int j = 0; j < n; j++){
a[(i + j) % n] = (a[i] - 1 + j) % n + 1;
}
break;
}
}
// cout << v.size() << endl;
sort(v.begin(), v.end());
int p = 0, l = 0;
while(p < v.size()){
replacementSeq[l] = a[v[p].se];
// cout << a[v[p].se] << ' ';
a[v[p].se] = n + l + 1;
l++;
if(a[v[p].se] == v[p].fi) p++;
}
// cout << endl;
// cout << l;
return l;
}
int calc(int x, int p){
pot[0] = x;
for(int i = 1; i < LOG; i++){
pot[i] = mul(pot[i - 1], pot[i - 1]);
}
int ret = 1;
for(int i = 0; i < LOG; i++){
if(p & (1 << i)) ret = mul(ret, pot[i]);
}
return ret;
}
int countReplacement(int n, int inputSeq[]){
if(!valid(n, inputSeq)) return 0;
for(int i = 0; i < n; i++){
a[i] = inputSeq[i];
}
for(int i = 0; i < n; i++){
if(a[i] > n) v.push_back({a[i], i});
}
// for(int i = n - 1; i >= 0; i--){
// if(a[i] <= n || !i){
// for(int j = 0; j < n; j++){
// a[(i + j) % n] = (a[i] - 1 + j) % n + 1;
// }
// break;
// }
// }
// cout << v.size() << endl;
// cout << v.size() << endl;
// if(v.size() == 0) return 1;
sort(v.begin(), v.end());
// for(int i = 0; i < v.size(); i++){
// cout << v[i].fi << ' ' << v[i].se << endl;
// }
int p = 0, l = n, ans = 1;
// while(p < v.size()){
// l++;
// if(a[v[p].se] == l){
// p++;
// continue;
// }
// ans = mul(ans, v.size() - p);
// }
int zad = n;
for(int i = 0; i < v.size(); i++){
// cout << v[i].fi << ' ' << zad << ": ";
// cout << v.size() - i << ' ' << v[i].fi - zad - 1 << endl;
ans = mul(ans, calc(v.size() - i, v[i].fi - zad - 1));
zad = v[i].fi;
}
// cout << endl;
// cout << l;
if(v.size() == n) ans = mul(ans, n);
return ans;
}
//int main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
//
// int n;
// cin >> n;
// int inputSeq[n];
// for(int i = 0; i < n; i++){
// cin >> inputSeq[i];
// }
// cout << countReplacement(n, inputSeq);
//
// return 0;
//}
Compilation message (stderr)
# | 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... |