Submission #27765

#	Time	Username	Problem	Language	Result	Execution time	Memory
27765		zoomswk	Gondola (IOI14_gondola)	C++14	100 / 100	109 ms	8680 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

map<int, int> occ;

int valid(int n, int inputSeq[]){
    for(int i=0; i<n; i++){
        inputSeq[i]--;
        if(occ[inputSeq[i]]) return 0;
        occ[inputSeq[i]] = 1;
    }
    int must = -1;
    for(int i=0; i<n; i++) if(inputSeq[i] < n) must = i;
    if(must == -1) return 1;
    for(int i=0; i<n; i++) if(inputSeq[i] < n && (inputSeq[i]+n+must-i)%n != inputSeq[must]) return 0;
    return 1;
}

//----------------------

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    int inputSeq[100005];
    for(int i=0; i<n; i++) gondolaSeq[i]--;
    int must = -1;
    for(int i=0; i<n; i++) if(gondolaSeq[i] < n) must = i;
    if(must == -1){
        for(int i=0; i<n; i++) inputSeq[i] = i;;
    } else{
        int cur = gondolaSeq[must];
        for(int i=must-1; i>=0; i--){
            cur--;
            if(cur < 0) cur += n;
            inputSeq[i] = cur;
        }
        cur = gondolaSeq[must];
        for(int i=must+1; i<n; i++){
            cur++;
            if(cur >= n) cur -= n;
            inputSeq[i] = cur;
        }
    }
    priority_queue<pair<int, int>> pq;
    for(int i=0; i<n; i++) if(gondolaSeq[i] >= n) pq.push({-gondolaSeq[i], i});
    int ptr = n-1;
    int sz = 0;
    while(!pq.empty()){
        int num = -pq.top().first;
        int pos = pq.top().second;
        pq.pop();
        while(ptr < num){
            replacementSeq[sz++] = inputSeq[pos]+1;
            inputSeq[pos] = ++ptr;
        }
    }
    return sz;
}

//----------------------

const int MOD = (1e9)+9;

long long poww(int base, int to){
    long long res = 1;
    long long cur = base;
    while(to){
        if(to&1) res *= cur, res %= MOD;
        cur *= cur;
        cur %= MOD;
        to >>= 1;
    }
    return res;
}

int countReplacement(int n, int inputSeq[]){
    if(!valid(n, inputSeq)) return 0;
    long long res = 1;
    priority_queue<int> pq;
    int cnt = 0;
    for(int i=0; i<n; i++) if(inputSeq[i] >= n){ pq.push(-inputSeq[i]); cnt++; }
    int ptr = n-1;
    if(cnt == n) res = n;
    while(!pq.empty()){
        int num = -pq.top();
        pq.pop();
        res *= poww(cnt, num-ptr-1);
        res %= MOD;
        cnt--;
        ptr = num;
    }
    return res;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10