Submission #412763

#	Time	Username	Problem	Language	Result	Execution time	Memory
412763		KoD	Last supper (IOI12_supper)	C++17	34 / 100	564 ms	21228 KiB

advisor

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

template <class T>
using Vec = std::vector<T>;

void write(const int width, const int bit) {
    for (int i = 0; i < width; ++i) {
        WriteAdvice(bit >> i & 1);
    }
}

void ComputeAdvice(int *C, int N, int K, int M) {
    Vec<Vec<int>> idx(N);
    for (int i = 0; i < N; ++i) {
        idx[i].push_back(N);
    }
    for (int i = N - 1; i >= 0; --i) {
        idx[C[i]].push_back(i);
    }
    std::map<int, int> map;
    std::set<std::pair<int, int>> que;
    for (int i = 0; i < K; ++i) {
        map[i] = i;
        que.emplace(idx[i].back(), i);
    }
    int width = 0;
    while ((1 << width) <= K) width += 1;
    for (int i = 0; i < N; ++i) {
        if (que.find(std::make_pair(idx[C[i]].back(), C[i])) == que.end()) {
            const auto [t, j] = *que.rbegin();
            que.erase(std::make_pair(t, j));
            write(width, map[j]);
            map[C[i]] = map[j];
        } 
        else {
            write(width, K);
            que.erase(std::make_pair(idx[C[i]].back(), C[i]));
        }
        idx[C[i]].pop_back();
        que.emplace(idx[C[i]].back(), C[i]);
    }
}

assistant

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

template <class T>
using Vec = std::vector<T>;

int read(unsigned char *A, const int width) {
    static int idx = 0;
    int bit = 0;
    for (int i = 0; i < width; ++i) {
        if (A[idx++]) {
            bit += 1 << i;
        }
    }
    return bit;
}

void Assist(unsigned char *A, int N, int K, int R) {
    std::map<int, int> map;
    Vec<int> cur(K);
    for (int i = 0; i < K; ++i) {
        cur[i] = i;
    }
    int width = 0;
    while ((1 << width) <= K) width += 1;
    for (int i = 0; i < N; ++i) {
        const auto c = GetRequest();
        const auto k = read(A, width);
        if (k != K) {
            const auto j = cur[k];
            PutBack(j);
            cur[k] = c;
        }
    }
}

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