Submission #166613

#	Time	Username	Problem	Language	Result	Execution time	Memory
166613		TAISA_	Gondola (IOI14_gondola)	C++14	60 / 100	46 ms	4600 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
int valid(int n, int inputSeq[]) {
    int b = -1;
    set<int> st;
    for (int i = 0; i < n; i++) {
        if (st.count(inputSeq[i])) {
            return 0;
        }
        st.insert(inputSeq[i]);
        if (inputSeq[i] <= n) {
            if (b == -1) {
                b = inputSeq[i];
            } else {
                if (b == n) {
                    if (inputSeq[i] != 1) {
                        return 0;
                    }
                    b = 1;
                } else {
                    if (inputSeq[i] != b + 1) {
                        return 0;
                    }
                    b++;
                }
            }
        } else {
            if (b != -1) {
                b++;
            }
        }
    }
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    int ma = -1;
    vector<int> co(250010), idx(n);
    int id = 0;
    int b = -1;
    for (int i = 0; i < n; i++) {
        if (gondolaSeq[i] <= n) {
            if (b == -1) {
                b = gondolaSeq[i];
                for (int j = i; j < n; j++) {
                    idx[j] = b;
                    b++;
                    if (b == n + 1) {
                        b = 1;
                    }
                }
                for (int j = 0; j < i; j++) {
                    idx[j] = b;
                    b++;
                    if (b == n + 1) {
                        b = 1;
                    }
                }
                break;
            }
        }
    }
    if (b == -1) {
        for (int i = 0; i < n; i++) {
            idx[i] = i + 1;
        }
    }
    vector<P> v;
    for (int i = 0; i < n; i++) {
        if (gondolaSeq[i] > n) {
            ma = max(ma, gondolaSeq[i]);
            v.push_back(P(gondolaSeq[i], i));
            co[gondolaSeq[i]] = 1;
        }
    }
    sort(v.begin(), v.end());
    int t = n + 1;
    for (int i = 0; i < v.size(); i++) {
        replacementSeq[id] = idx[v[i].second];
        id++;
        for (int j = t; j < gondolaSeq[v[i].second]; j++) {
            replacementSeq[id] = j;
            id++;
        }
        t = gondolaSeq[v[i].second] + 1;
    }
    return id;
}

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

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

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:82:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); i++) {
                     ~~^~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:100:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• 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: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10