oj.uz

답안 #102344

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102344 2019-03-24T12:24:41 Z naoai 최후의 만찬 (IOI12_supper) C++14
100 / 100
 119 ms 9432 KB 
#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]);
    }
}

#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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 776 KB Output is correct
2 Correct 5 ms 804 KB Output is correct
3 Correct 6 ms 812 KB Output is correct
4 Correct 6 ms 944 KB Output is correct
5 Correct 7 ms 1096 KB Output is correct
6 Correct 9 ms 1104 KB Output is correct
7 Correct 7 ms 1280 KB Output is correct
8 Correct 10 ms 1024 KB Output is correct
9 Correct 10 ms 1024 KB Output is correct
10 Correct 11 ms 1536 KB Output is correct
11 Correct 10 ms 1096 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1536 KB Output is correct
2 Correct 43 ms 4848 KB Output is correct
3 Correct 80 ms 9080 KB Output is correct
4 Correct 83 ms 7152 KB Output is correct
5 Correct 80 ms 7344 KB Output is correct
6 Correct 86 ms 7896 KB Output is correct
7 Correct 79 ms 8920 KB Output is correct
8 Correct 80 ms 7648 KB Output is correct
9 Correct 100 ms 7152 KB Output is correct
10 Correct 80 ms 9432 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 6640 KB Output is correct
2 Correct 80 ms 9136 KB Output is correct
3 Correct 103 ms 9432 KB Output is correct
4 Correct 72 ms 9432 KB Output is correct
5 Correct 83 ms 9176 KB Output is correct
6 Correct 91 ms 9176 KB Output is correct
7 Correct 90 ms 9176 KB Output is correct
8 Correct 104 ms 8672 KB Output is correct
9 Correct 99 ms 9432 KB Output is correct
10 Correct 87 ms 9176 KB Output is correct

Subtask #4
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1024 KB Output is correct
2 Correct 9 ms 1096 KB Output is correct
3 Correct 8 ms 1024 KB Output is correct
4 Correct 7 ms 1096 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct
7 Correct 10 ms 1280 KB Output is correct
8 Correct 10 ms 1536 KB Output is correct
9 Correct 11 ms 1280 KB Output is correct
10 Correct 9 ms 1280 KB Output is correct

Subtask #5
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 7896 KB Output is correct - 120000 bits used
2 Correct 98 ms 7896 KB Output is correct - 122000 bits used
3 Correct 119 ms 8040 KB Output is correct - 125000 bits used
4 Correct 84 ms 8160 KB Output is correct - 125000 bits used
5 Correct 102 ms 7896 KB Output is correct - 125000 bits used
6 Correct 100 ms 8176 KB Output is correct - 125000 bits used
7 Correct 104 ms 8184 KB Output is correct - 124828 bits used
8 Correct 80 ms 8160 KB Output is correct - 124910 bits used
9 Correct 106 ms 8176 KB Output is correct - 125000 bits used
10 Correct 84 ms 7384 KB Output is correct - 125000 bits used