Submission #103782

#	Time	Username	Problem	Language	Result	Execution time	Memory
103782		alexpetrescu	최후의 만찬 (IOI12_supper)	C++14	91 / 100	2545 ms	6912 KiB

advisor

#include "advisor.h"
#include <vector>
#include <cstdio>

#define MAXN 100009

int heap[MAXN], poz[MAXN], d[MAXN];

inline void mySwap(int p, int q) {
    int aux = heap[p];
    heap[p] = heap[q];
    heap[q] = aux;
    poz[heap[p]] = p;
    poz[heap[q]] = q;
}

inline void urcare(int p) {
    while (p > 1 && d[heap[p]] > d[heap[p / 2]]) {
        mySwap(p, p / 2);
        p /= 2;
    }
}

inline void coborare(int p) {
    int q;
    bool f = 1;
    while (f && (q = 2 * p) <= heap[0]) {
        if (q < heap[0] && d[heap[q + 1]] > d[heap[q]])
            q++;
        if (d[heap[q]] > d[heap[p]]) {
            mySwap(p, q);
            p = q;
        } else
            f = 0;
    }
}

void ComputeAdvice(int *C, int N, int K, int M) {
    for (int i = 0; i < N; i++)
        d[i] = N;
    for (int i = 0; i < N; i++)
        if (d[C[i]] == N)
            d[C[i]] = i;

    for (int i = 0; i < K; i++)
        heap[++heap[0]] = i, poz[i] = i + 1;
    for (int i = heap[0]; i > 0; i--)
        coborare(i);

    std::vector < int > urm(N), last(N, N);
    for (int i = N - 1; i >= 0; i--) {
        urm[i] = last[C[i]];
        last[C[i]] = i;
    }

    std::vector < bool > ans(N + K, 1);
    std::vector < int > moment(N, -1);
    for (int i = 0; i < K; i++)
        moment[i] = i;

    for (int i = 0; i < N; i++) {
        if (poz[C[i]]) {
            d[C[i]] = urm[i];
            urcare(poz[C[i]]);
        } else {
            ans[moment[heap[1]]] = 0;
            poz[heap[1]] = 0;
            heap[1] = C[i];
            poz[C[i]] = 1;
            d[heap[1]] = urm[i];
            coborare(1);
        }
        moment[C[i]] = i + K;
    }

    for (int i = 0; i < N + K; i++)
        WriteAdvice(ans[i]);
}

assistant

#include "assistant.h"
#include <vector>

void Assist(unsigned char *A, int N, int K, int R) {
    std::vector < int > v(K), t(N, 0);
    for (int i = 0; i < K; i++)
        v[i] = i, t[i] = A[i];
    for (int i = 0; i < N; i++) {
        int x = GetRequest();
        int p = 0;
        while (p < K && v[p] != x)
            p++;
        if (p >= K) {
            p = 0;
            while (t[v[p]])
                p++;
            PutBack(v[p]);
            v[p] = x;
        }
        t[x] = A[i + K];
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 9 / 9
• Subtask 4: 35 / 35
• Subtask 5: 39 / 39