제출 #159947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
159947		rama_pang	곤돌라 (IOI14_gondola)	C++14	25 / 100	18 ms	1784 KiB

gondola

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


int valid(int n, int inputSeq[]) {
    deque<int> gondola(n);
    for (int i = 0; i < n; i++) gondola[i] = inputSeq[i];

    int pivot = -1;
    for (int i = 0; i < n; i++) if (gondola[i] <= n) pivot = gondola[i];
    for (int i = 0; i < n + n && pivot != -1; i++) {
        if (gondola[pivot] == pivot + 1) break;
        gondola.push_back(gondola.front());
        gondola.pop_front();
    }

    for (int i = 0; i < n; i++) if (gondola[i] != i + 1 && gondola[i] <= n) return 0;

    return 1;
}


int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    deque<int> gondola(n);
    for (int i = 0; i < n; i++) gondola[i] = gondolaSeq[i];

    int pivot = -1;
    for (int i = 0; i < n; i++) if (gondola[i] <= n) pivot = gondola[i];
    for (int i = 0; i < n + n && pivot != -1; i++) {
        if (gondola[pivot] == pivot + 1) break;
        gondola.push_back(gondola.front());
        gondola.pop_front();
    }

    vector<pair<int, int>> replace;
    vector<int> ans;

    for (int i = 0; i < n; i++) if (gondola[i] > n) replace.emplace_back(gondola[i], i + 1);

    sort(replace.begin(), replace.end());
    int cur = n + 1;
    for (int i = 0; i < replace.size(); i++) {
        ans.push_back(replace[i].second);
        for (int j = cur; j < replace[i].first; j++) {
            ans.push_back(j);
        }
        cur = replace[i].first + 1;
    }

    for (int i = 0; i < ans.size(); i++) replacementSeq[i] = ans[i];

    return ans.size();
}

using lint = long long;
const lint MOD = 1e9 + 9;

lint pw(lint n, lint x) {
    if (x == 0) return 1;
    if (x == 1) return n;

    lint res = pw(n, x / 2);
    res %= MOD;
    res *= res;
    res %= MOD;
    if (x & 1) res *= n;
    res %= MOD;
    return res;
}

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

    deque<int> gondola(n);
    for (int i = 0; i < n; i++) gondola[i] = inputSeq[i];

    vector<int> replace;
    for (int i = 0; i < n; i++) if (gondola[i] > n) replace.emplace_back(gondola[i]);
    sort(replace.begin(), replace.end());

    lint active = replace.size();
    lint cur = n + 1;
    lint res = 1;
    
    for (int i = 0; i < replace.size(); i++) {
        res *= pw(active, replace[i] - cur);
        cur = replace[i] + 1;
        active--;
        res %= MOD;
    }
    
    return (int)res;
}

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

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < replace.size(); i++) {
                     ~~^~~~~~~~~~~~~~~~
gondola.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ans.size(); i++) replacementSeq[i] = ans[i];
                     ~~^~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < replace.size(); i++) {
                     ~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10