| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 8525 | 2014-09-16T04:01:37 Z | gs14004 | Gondola (IOI14_gondola) | C++ | 0 ms | 0 KB |
#include <cstdio>
#include <algorithm>
#include <queue>
#include <utility>
#include <set>
#include "gondola.h"
using namespace std;
typedef pair<int,int> pi;
int valid(int n, int inputSeq[]){
int v[250005]={};
for (int i=0; i<n; i++) {
if(v[inputSeq[i]]) return 0;
v[inputSeq[i]] = 1;
}
int piv = -1;
for (int i=0; i<n; i++) {
if(inputSeq[i] <= n){
if(piv == -1){
piv = i;
}
else{
int res = i + (inputSeq[piv] - piv) + n;
res %= n;
if(res == 0) res = n;
if(inputSeq[i] != res) return 0;
}
}
}
return 1;
}
priority_queue<pi,vector<pi>,greater<pi> > pq, pq2;
set<int> mp;
void replacement(int n, int gondolaSeq[], int replacementSeq[]){
int piv = 0, piv2 = n+1, piv3 = 0;
for (int i=0; i<n; i++) {
if(gondolaSeq[i] <= n){
piv = gondolaSeq[i] - i - 1+ n;
piv %= n;
}
}
int newSeq[100005] = {};
for (int i=0; i<n; i++) {
newSeq[i] = gondolaSeq[(i + n - piv)%n];
if(newSeq[i] > n) pq.push(pi(newSeq[i],i+1));
}
while (!pq.empty()) {
pi x = pq.top();
pq.pop();
replacementSeq[piv3++] = x.second;
for (int i=piv2; i<x.first; i++) {
replacementSeq[piv3++] = i;
}
piv2 = x.first + 1;
}
}
int countReplacement(int n, int inputSeq[]){
if(!valid(n,inputSeq)) return 0;
int piv = 0, piv2 = n + 1, cnt = 0;
long long mod = 1e9 + 9;
long long res = 1;
int exception = 1;
for (int i=0; i<n; i++) {
if(inputSeq[i] <= n){
piv = inputSeq[i] - i - 1+ n;
piv %= n;
exception = 0;
}
}
int newSeq[100005] = {};
for (int i=0; i<n; i++) {
newSeq[i] = inputSeq[(i + n - piv)%n];
if(newSeq[i] > n) {
cnt++;
mp.insert(newSeq[i]);
}
}
if(exception) res = cnt;
while (cnt) {
if(mp.find(piv2) == mp.end()) res *= cnt;
else cnt--;
res %= mod;
piv2++;
}
return (int)res;
}