oj.uz

Submission #103784

# Submission time Handle Problem Language Result Execution time Memory
103784 2019-04-02T16:00:27 Z alexpetrescu Last supper (IOI12_supper) C++14
100 / 100
 120 ms 7164 KB 
#include "advisor.h"
#include <vector>

#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) {
    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;
    }

    for (int i = 0; i < K; i++)
        d[i] = last[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 < 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]);
}

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

std::set < int > s;

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 < K; i++)
        if (t[i] == 0)
            s.insert(i);
    std::vector < int > avem(N, 0);
    for (int i = 0; i < K; i++)
        avem[i] = 1;

    for (int i = 0; i < N; i++) {
        int x = GetRequest();
        if (!avem[x]) {
            int y = *(s.begin());
            PutBack(y);
            s.erase(s.begin());
            avem[y] = 0;
            avem[x] = 1;
            t[x] = A[i + K];
            if (t[x] == 0)
                s.insert(x);
        } else {
            if (t[x] == 1 && A[i + K] == 0)
                s.insert(x);
            else if (t[x] == 0 && A[i + K] == 1)
                s.erase(s.lower_bound(x));
            t[x] = A[i + K];
        }
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 772 KB Output is correct
4 Correct 5 ms 920 KB Output is correct
5 Correct 9 ms 1036 KB Output is correct
6 Correct 9 ms 1056 KB Output is correct
7 Correct 6 ms 1056 KB Output is correct
8 Correct 6 ms 1056 KB Output is correct
9 Correct 8 ms 1024 KB Output is correct
10 Correct 10 ms 1160 KB Output is correct
11 Correct 8 ms 1024 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1356 KB Output is correct
2 Correct 48 ms 3340 KB Output is correct
3 Correct 89 ms 6208 KB Output is correct
4 Correct 96 ms 6720 KB Output is correct
5 Correct 78 ms 6656 KB Output is correct
6 Correct 88 ms 6732 KB Output is correct
7 Correct 100 ms 7148 KB Output is correct
8 Correct 60 ms 5888 KB Output is correct
9 Correct 60 ms 6648 KB Output is correct
10 Correct 87 ms 7164 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 4944 KB Output is correct
2 Correct 104 ms 6064 KB Output is correct
3 Correct 84 ms 6072 KB Output is correct
4 Correct 88 ms 6076 KB Output is correct
5 Correct 97 ms 6176 KB Output is correct
6 Correct 106 ms 5956 KB Output is correct
7 Correct 84 ms 6088 KB Output is correct
8 Correct 75 ms 5928 KB Output is correct
9 Correct 100 ms 6656 KB Output is correct
10 Correct 110 ms 6200 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1060 KB Output is correct
2 Correct 7 ms 1064 KB Output is correct
3 Correct 8 ms 1056 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Correct 8 ms 1056 KB Output is correct
9 Correct 10 ms 1056 KB Output is correct
10 Correct 10 ms 1024 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 5820 KB Output is correct - 120000 bits used
2 Correct 90 ms 6016 KB Output is correct - 122000 bits used
3 Correct 120 ms 6072 KB Output is correct - 125000 bits used
4 Correct 82 ms 6076 KB Output is correct - 125000 bits used
5 Correct 86 ms 5976 KB Output is correct - 125000 bits used
6 Correct 91 ms 6064 KB Output is correct - 125000 bits used
7 Correct 80 ms 6208 KB Output is correct - 124828 bits used
8 Correct 78 ms 6084 KB Output is correct - 124910 bits used
9 Correct 82 ms 5896 KB Output is correct - 125000 bits used
10 Correct 79 ms 5928 KB Output is correct - 125000 bits used