Submission #159958

#	Time	Username	Problem	Language	Result	Execution time	Memory
159958		rama_pang	Gondola (IOI14_gondola)	C++14	100 / 100	78 ms	6520 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];
    pivot--;
    for (int i = 0; i < n + n && pivot >= 0; 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;
    map<int, int> cnt;
    for (int i = 0; i < n; i++) cnt[gondola[i]]++;
    for (auto i : cnt) if (i.second > 1) 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];
    pivot--;
    for (int i = 0; i < n + n && pivot >= 0; 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<lint> gondola(n);
    for (int i = 0; i < n; i++) gondola[i] = inputSeq[i];

    vector<lint> 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;
    if (active == n) res = n;
    for (int i = 0; i < replace.size(); i++) {
        assert(cur <= replace[i]);
        res *= pw(active - i, replace[i] - cur);
        cur = replace[i] + 1;
        res %= MOD;
    }
    
    return (int)res;
}

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < replace.size(); i++) {
                     ~~^~~~~~~~~~~~~~~~
gondola.cpp:53: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:88: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: 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