Submission #1229368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229368		LucaIlie	Gondola (IOI14_gondola)	C++20	15 / 100	5 ms	584 KiB

gondola

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

using namespace std;

const int INF = 1e9 + 1;
const int MAX_N = 1e5;

int valid(int n, int inputSeq[]) {
    int pos = 0, minn = INF + 1;
    for (int i = 0; i < n; i++) {
        if (inputSeq[i] < minn) {
            minn = inputSeq[i];
            pos = i;
        }
    }
    int a = minn;
    int i = pos;
    do {
        if (inputSeq[i] <= n) {
            if (inputSeq[i] != a)
                return false;
            a++;
        }
        i = (i + 1) % n;
    } while (i != pos);

    return true;
}

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

int realVal[MAX_N];

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    int pos = 0, minn = INF + 1;
    for (int i = 0; i < n; i++) {
        if (gondolaSeq[i] < minn) {
            minn = gondolaSeq[i];
            pos = i;
        }
    }
    int a = minn;
    int i = pos;
    vector<pair<int, int>> v;
    do {
        realVal[i] = a;
        if (gondolaSeq[i] <= n) 
            a = a % n + 1;
        else
            v.push_back({gondolaSeq[i], i});
        i = (i + 1) % n;
    } while (i != pos);

    int rep = n + 1;
    sort(v.begin(), v.end());
    int l = 0;
    for (auto p: v) {
        replacementSeq[l++] = realVal[p.second];
        while (rep < p.first) {
            replacementSeq[l++] = rep;
            rep++;
        }
    }

    return l;
}

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

int countReplacement(int n, int inputSeq[])
{
  return -3;
}

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