제출 #582297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
582297		jasmin	곤돌라 (IOI14_gondola)	C++14	100 / 100	51 ms	5432 KiB

gondola

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

const int inf=1e9+9;
const int mod=1e9+9;

vector<int> reorder(int n, int s[]){
    int small=inf; int ind=-1;
    for(int i=0; i<n; i++){
        if(s[i]<small){
            small=s[i];
            ind=i;
        }
    }

    if(n<small){
        vector<int> ans(n);
        for(int i=0; i<n; i++){
            ans[i]=s[i];
        }
        return ans;
    }
    int start=(n+ind-(small-1))%n;
    vector<int> ans(n);
    for(int i=0; i<n; i++){
        ans[i]=s[(start+i)%n];
    }
    return ans;
}

int valid(int n, int inputSeq[]){
    vector<int> s=reorder(n, inputSeq);
    set<int> used;
    for(int i=0; i<n; i++){
        if(s[i]!=i+1){
            if(s[i]<=n || used.find(s[i])!=used.end()){
                return false;
            }
            used.insert(s[i]);
        }
    }
    return true;
}

int maximum(vector<int>& s){
    int ans=-1;
    for(auto e: s){
        ans=max(ans, e);
    }
    return ans;
}

int replacement(int n, int gondolaSeq[], int ans[]){
    vector<int> s=reorder(n, gondolaSeq);
    int size=maximum(s)-n;
    
    for(int i=0; i<size; i++){
        ans[i]=-1;
    }

    set<int> usable;
    for(int i=0; i<n; i++){
        if(s[i]>n){
            ans[s[i]-n-1]=i;
            usable.insert(i);
        }
    }
    iota(s.begin(), s.end(), 1);
    for(int i=0; i<size; i++){
        if(ans[i]==-1){
            int ind=*usable.begin();
            ans[i]=s[ind];
            s[ind]=n+i+1;
        }
        else{
            int ind=ans[i];
            usable.erase(ind);
            ans[i]=s[ind];
            s[ind]=n+i+1;
        }
    }

    return size;
}

int minimum(vector<int>& s){
    int ans=inf;
    for(auto e: s){
        ans=min(ans, e);
    }
    return ans;
}

long long fastpow(int a, int e){
    if(e==0) return 1;
    long long ans=fastpow(a, e/2);
    ans=(ans*ans)%mod;
    if(e%2==1){
        ans*=a;
        ans%=mod;
    }
    return ans;
}

int countReplacement(int n, int inputSeq[]){
    if(!valid(n, inputSeq)) return 0;

    vector<int> s=reorder(n, inputSeq);
    
    long long ans=1ll;
    int usable=0;
    vector<int> b;
    for(int i=0; i<n; i++){
        if(s[i]>n){
            usable++;
            b.push_back(s[i]);
        }
    }
    sort(b.begin(), b.end());
    int l=n+1;
    for(auto e: b){
        ans*=fastpow(usable, e-l);
        ans%=mod;
        l=e+1;
        usable--;
    }

    if(minimum(s)>n){
        ans*=n;
        ans%=mod;
    }
    return ans;
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    int s[n];
    for(int i=0; i<n; i++){
        cin >> s[i];
    }
    cout << valid(n, s) << "\n";
    
    int rep[n*3];
    int size=replacement(n, s, rep);
    cout << size << "\n";
    for(auto e: rep){
        cout << e << " ";
    }
    cout << "\n";
    cout << countReplacement(n, s) << "\n";
}*/

• 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