제출 #66381

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66381		someone_aa	Gondola (IOI14_gondola)	C++17	100 / 100	76 ms	10536 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 250100;
const ll mod = 1000000009;
map<int, bool>exist;
int fin_val[maxn];
ll cnt[maxn];

int valid(int n, int arr[]) {
    bool check = true;

    for(int i=1;i<n;i++) {
        if(arr[i] > n) continue;
        else if(arr[i] == 1) {
            if(arr[i-1] < n)
                check = false;
        }
        else {
            if(arr[i-1] <= n && arr[i-1] != arr[i] - 1) check = false;
        }
    }

    sort(arr, arr+n);
    for(int i=1;i<n;i++) {
        if(arr[i] == arr[i-1]) check = false;
    }
    if(check) return 1;
    else return 0;
}

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

int replacement(int n, int arr[], int replacementSeq[]) {
    int maxm = 0;
    int found_i = 0, st_val = 1;
    for(int i=0;i<n;i++) {
        exist[arr[i]] = true;
        if(arr[i] <= n) {
            found_i = i;
            st_val = arr[i];
        }
        maxm = max(maxm, arr[i]);
    }
    exist[n] = true;
    int l = maxm - n;


    for(int i=found_i;i<n;i++) {
        fin_val[i] = st_val;
        st_val++;
        if(st_val == n + 1) st_val = 1;
    }

    for(int i=0;i<found_i;i++) {
        fin_val[i] = st_val;
        st_val++;
        if(st_val == n + 1) st_val = 1;
    }

    for(int i=0;i<n;i++) {
        while(!exist[arr[i]-1] && arr[i] > n) {
            replacementSeq[arr[i]-n-1] = arr[i] - 1;
            arr[i]--;
        }
        if(arr[i] > n) replacementSeq[arr[i]-n-1] = fin_val[i];
    }

    return l;
}

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

ll power(ll a, ll b) {
    if(b == 0) return 1LL;
    else if(b == 1) return 1LL * a % mod;
    else {
        if(b%2 == 0) {
            ll half = power(a, b/2) % mod;
            return (1LL*half * half)% mod;
        }
        else if(b%2==1) {
            return (1LL*a*power(a, b-1)) % mod;
        }
    }
}

int countReplacement(int n, int arr[]) {
    if(!valid(n, arr)) return 0;
    vector<ll>nums;
    for(int i=0;i<n;i++) {
        if(arr[i] > n) nums.push_back(arr[i]);
    }
    nums.push_back(n);
    sort(nums.begin(), nums.end());

    ll result = 1LL;
    for(int i=1;i<nums.size();i++) {
        ll diff = 1LL * nums[i] - nums[i-1] - 1;
        ll p = 1LL * int(nums.size()) - i;
        result *= 1LL*power(p, diff);
        result %= mod;
    }

    if(nums.size() == n + 1) {
        result *= n;
        result %= mod;
    }
    return result;
}

/*int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70};
    int arr2[1];
    cout<<countReplacement(7, arr);
}*/

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

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:99:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<nums.size();i++) {
                 ~^~~~~~~~~~~~
gondola.cpp:106:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(nums.size() == n + 1) {
        ~~~~~~~~~~~~^~~~~~~~
gondola.cpp: In function 'long long int power(long long int, long long int)':
gondola.cpp:87:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• 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