Submission #824118

#	Time	Username	Problem	Language	Result	Execution time	Memory
824118		annabeth9680	Gondola (IOI14_gondola)	C++17	100 / 100	53 ms	6424 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll MOD = 1e9+9;
int valid(int n, int inputSeq[]){
    set<int> s;
    int pos = -1;
    for(int i = 0;i<n;++i){
        if(s.find(inputSeq[i]) != s.end()) return 0;
        if(inputSeq[i] <= n && pos == -1){
            pos = i;
        }
        s.insert(inputSeq[i]);
    }
    if(pos == -1) return 1;
    for(int i = 0;i<n;++i){
        if(inputSeq[i] <= n && i != pos){
            int d = (inputSeq[pos]+i-pos+n)%n;
            if(d == 0) d = n;
            if(d != inputSeq[i]) return 0;
        }
    }
    return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    int shift = -1;
    for(int i = 0;i<n;++i){
        if(gondolaSeq[i] <= n){
            shift = (gondolaSeq[i]-i-1+n)%n;
        }
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    for(int i = 0;i<n;++i){
        int d = (i-shift+n)%n;
        if(gondolaSeq[d] > n){
            pq.push({gondolaSeq[d],i+1});
        }
    }
    int l = 0, cur = n+1;
    while(!pq.empty()){
        pair<int,int> p = pq.top(); pq.pop();
        replacementSeq[l++] = p.second;
        for(int i = cur;i<p.first;++i) replacementSeq[l++] = i;
        cur = p.first+1;
    }
    return l;
}
ll binpow(int x, int k){
    ll ans = 1, p = x;
    while(k != 0){
        if(k & 1) ans *= p;
        p *= p;
        p %= MOD;
        ans %= MOD;
        k /= 2;
    }
    return ans;
}
int countReplacement(int n, int inputSeq[]){
    if(!valid(n,inputSeq)) return 0;
    int newseq[100005] = {};
    int cnt = 0;
    for(int i = 0;i<n;++i){
        if(inputSeq[i] > n){
            newseq[cnt++] = inputSeq[i];
        }
    }
    sort(newseq,newseq+cnt);
    int last = n, cur = cnt; ll ans = 1;
    if(cnt == n) ans = n;
    for(int i = 0;i<cnt;++i){
        ans *= binpow(cur,newseq[i]-last-1);
        ans %= MOD;
        last = newseq[i];
        cur--;
    }
    return (int)ans;
}

• 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