제출 #103781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103781		SecretAgent007	곤돌라 (IOI14_gondola)	C++17	100 / 100	128 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;
}

const int mod = 1e9+9;

long long power(long long b, int n){
    long long ans = 1;
    while(n){
        if(n%2){
            ans*=b;
            ans %= mod;
        }
        n/=2;
        b*=b;
        b%=mod;
    }
    return ans;
}

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

    vector< int > cnt;
    for(int i = 0; i < n; i++){
        if(inputSeq[i] > n){
            cnt.push_back(inputSeq[i]);
        }
    }

    sort(cnt.begin(), cnt.end());

    long long ans = 1;

    int last = n+1;

    for(int i = 0; i < (int)cnt.size(); i++){

        ans *= power(cnt.size()-i, cnt[i]-last);
        ans %= mod;
        last = cnt[i]+1;
    }
    if((int)cnt.size() == n) return ((long long)n*ans)%mod;
    return ans;
}
/*
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: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10