Submission #1363413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1363413		toma_ariciu	Gondola (IOI14_gondola)	C++20	25 / 100	4 ms	1348 KiB

gondola

#include "gondola.h"

#include <bits/stdc++.h>

using namespace std;

const int maxN = 250005;
int poz[maxN];

int valid(int n, int inputSeq[]) {
    for (int i = 1; i <= n; i++) {
        int x = inputSeq[i];
        if (poz[x]) {
            return 0;
        }
        poz[x] = i;
    }

    for (int i = 1; i < n; i++) {
        int diff = poz[i + 1] - poz[i];
        if (diff < 0) {
            diff += n;
        }
        if (diff != 1) {
            return 0;
        }
    }

    return 1;
}


int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    vector <int> extras;
    int root = -1;
    for (int i = 1; i <= n; i++) {
        int x = gondolaSeq[i - 1];
        if (x > n) {
            extras.push_back(x);
        } else {
            root = x;
        }
        poz[x] = i;

    }
    sort(extras.begin(), extras.end());
    int p = 0, last = n + 1;
    for (int i = 0; i < extras.size(); i++) {
        int x = extras[i];
        int trueNumber = (root + (poz[x] - poz[root] + n) % n) % n;
        if (trueNumber == 0) {
            trueNumber += n;
        }
        replacementSeq[p++] = trueNumber;
        while (last < extras[i]) {
            replacementSeq[p++] = last;
            last++;
        }
        last++;
    }

    return p;
}

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

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 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