제출 #102344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
102344		naoai	최후의 만찬 (IOI12_supper)	C++14	100 / 100	119 ms	9432 KiB

advisor

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

using namespace std;

const int nmax = 1e5;

static int viz[nmax + 1], urm[nmax + 1];
int lst[nmax + 1];
bool adv[2 * nmax + 1];

struct str {
    int x, ind, u;

    str () {}
    str (int _x, int _ind, int _u) {
        x = _x, ind = _ind, u = _u;
    }

    bool operator < (const str &shp) const {
        if (u != shp.u) return u < shp.u;
        return x > shp.x;
    }
};

priority_queue<str> h;

void ComputeAdvice(int *v, int N, int K, int M) {
    for (int i = 0; i < N; ++ i)
        lst[i] = 1 << 30;

    for (int i = N - 1; i >= 0; -- i) {
        urm[i] = lst[v[i]];
        lst[v[i]] = i;
    }

    for (int i = 0; i < K; ++ i) {
        h.push(str(i, i, lst[i]));
        viz[i] = 1;
    }

    for (int i = 0; i < N; ++ i) {
        if (viz[v[i]] == 0) {
            while (!h.empty() && h.top().u <= i) {
                h.pop();
            }

            str x = h.top();
            h.pop();

            adv[x.ind] = 1;
            viz[x.x] = 0;
        }

        viz[v[i]] = 1;
        h.push(str(v[i], i + K, urm[i]));
    }

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

assistant

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

using namespace std;

const int nmax = 1e5;

bool viz[nmax + 1];
queue<int> q;

void Assist(unsigned char *A, int N, int K, int R) {
    for (int i = 0; i < K; ++ i) {
        viz[i] = 1;
        if (A[i] == 1)
            q.push(i);
    }

    for (int i = 0; i < N; ++ i) {
        int c = GetRequest();
        if (viz[c] == 0) {
            assert(q.size());
            PutBack(q.front());
            viz[q.front()] = 0;
            q.pop();
        }

        viz[c] = 1;

        if (A[i + K] == 1)
            q.push(c);
    }
}

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