제출 #1229394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229394		LucaIlie	Gondola (IOI14_gondola)	C++20	25 / 100	9 ms	628 KiB

gondola

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

using namespace std;

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

map<int, int> frecv;

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++;
        } else {
            if (frecv[inputSeq[i]])
                return false;
            frecv[inputSeq[i]]++;
        }
        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;
        a = a % n + 1;
        if (gondolaSeq[i] > n) 
            v.push_back({gondolaSeq[i], i});
        i = (i + 1) % n;
    } while (i != pos);

    int rep = n;
    sort(v.begin(), v.end());
    int l = 0;
    for (auto p: v) {
        replacementSeq[l++] = realVal[p.second];
        rep++;
        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: 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