제출 #103775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103775		SecretAgent007	Gondola (IOI14_gondola)	C++17	55 / 100	80 ms	10104 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

int valid(int n, int inputSeq[]){

    int index = 0;
    int num = n;

    map< int, bool> visited;

    for(int i = 0; i < n; i++){
        if(visited[inputSeq[i]]) return 0;
        visited[inputSeq[i]] = true;
        if(inputSeq[i] <= num){
            num = inputSeq[i];
            index = i;
        }
    }

    int start = (index-num+1+n)%n;

    int curr = 1;

    for(int i = start; i < n; i++){
        if(inputSeq[i] <= n && inputSeq[i] != curr) return 0;
        curr++;
    }
    for(int j = 0; j < start; j++){
        if(inputSeq[j] <= n && inputSeq[j] != curr) return 0;
        curr++;
    }
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    int index = 0;
    int num = n;

    int maxi = 0;

    for(int i = 0; i < n; i++){
        if(gondolaSeq[i] <= num){
            num = gondolaSeq[i];
            index = i;
        }
        maxi = max(maxi, gondolaSeq[i]);
    }

    int start = (index-num+1+n)%n;

    if(gondolaSeq[index] > n) start = 0;

    int curr = 1;

    map<int, int> mape;

    vector< int > current(n+1);

    for(int i = 1; i <= n; i++){
        current[i] = i;
    }

    int in;

    for(int i = start; i < n; i++){
        mape[gondolaSeq[i]] = curr;
        if(gondolaSeq[i] == maxi) in = curr;
        curr++;
    }
    for(int j = 0; j < start; j++){
        mape[gondolaSeq[j]] = curr;
        if(gondolaSeq[j] == maxi) in = curr;
        curr++;
    }

    int c = 0;

    for(int i = n+1; i <= maxi; i++){
        if(mape[i] != 0){
            replacementSeq[c] = current[mape[i]];
            current[mape[i]] = i;
        }else{
            replacementSeq[c] = current[in];
            current[in] = i;
        }
        c++;
    }

    return c;
}

int last;

map<int, bool> visited;
vector< int > ve;
vector< int > cnt;

const int mod = 1e9+9;

int dp(int curr, int n){
    if(curr >= n){
        return 1;
    }

    if(visited[curr]){
        return dp(curr+1, n);
    }

    long long  index = n-curr-1;
    long long nb = index;
    nb = nb%mod;

    long long tempo = ((nb*dp(curr+1,n))%mod)*(cnt[curr+1]-cnt[curr])%mod;
    return (tempo);
}

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

    ve.resize(n);
    cnt.resize(0);

    int mini = mod;

    for(int i = 0; i < n; i++){
        mini = min(mini, inputSeq[i]);
        last = max(last, inputSeq[i]);
        ve[i] = inputSeq[i];
        if(inputSeq[i] > n){
            cnt.push_back(inputSeq[i]);
        }
        //cnt[i] = inputSeq[i];
        visited[inputSeq[i]] = true;
    }

    if(!visited[n+1]) cnt.push_back(n+1);
    sort(cnt.begin(), cnt.end());

    cnt.push_back(cnt.back());

    long long rep = dp(0, cnt.size()-1);

    /*for(int i = n-2; i >= 0; i--){
        if(cnt[i] < n+1) break;
        rep = ((rep*(n-i-1)%mod)*(cnt[i+1]-cnt[i]))%mod;
    }
    */
    if(mini >= n){
        long long ans = ((long long)n*rep)%mod;
        return ans;
    }

    return rep;
}
/*
int main(){
    int n;
    cin >> n;
    int v[n];
    int maxi = 0;
    for(int i = 0; i < n; i++){
        cin >> v[i];
        maxi = max(maxi, v[i]);
    }
    int ans[maxi-n];
    cout << replacement(n,v,ans) << endl;
    for(int a : ans){
        cout << a << ' ';
    }
    cout << endl;

    cout << "NUMBER " << countReplacement(n,v) << endl;
}*/

컴파일 시 표준 에러 (stderr) 메시지

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:85:43: warning: 'in' may be used uninitialized in this function [-Wmaybe-uninitialized]
             replacementSeq[c] = current[in];
                                           ^

• 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: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10