제출 #154022

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

advisor

#include<bits/stdc++.h>
#include "advisor.h"
using namespace std;


deque<int>v[100002];
void ComputeAdvice(int *C, int N, int K, int M)
{
    for(int i = 0; i < N; ++i)
        v[C[i]].push_back(i);
    for(int i = 0; i < N; ++i)
        v[i].push_back((1<<20));
    set<pair<int, int> >cb;
    set<int>nr;
    for(int i = 0; i < K; ++i)
        cb.insert({v[i][0], i}), nr.insert(i);
    int act[100002];
    memset(act, 0, sizeof(act));
    int st[100002];
    for(int i = 0; i < K; ++i)
        st[i] = 1;
    int saved[100002];
    memset(saved, 0, sizeof(saved));
    int prv[100002];
    memset(prv, -1, sizeof(prv));
    for(int i = 0; i < N; ++i)
    {
        if(nr.find(C[i]) != nr.end())
        {
            if(C[i] < K && !saved[C[i]])
                saved[C[i]] = 1;
            cb.erase({v[C[i]][0], C[i]});
            v[C[i]].pop_front();
            cb.insert({v[C[i]][0], C[i]});
            if(prv[C[i]] != -1)
                act[prv[C[i]]] = 1;
            prv[C[i]] = i;
        }
        else
        {
            if((*cb.rbegin()).second < K)
            {
                int val = (*cb.rbegin()).second;
                if(val < K && !saved[val])
                    st[val] = 0, saved[val] = 1;
            }
            nr.erase((*cb.rbegin()).second);
            cb.erase(*cb.rbegin());
            nr.insert(C[i]);
            v[C[i]].pop_front();
            cb.insert({v[C[i]][0], C[i]});
            prv[C[i]] = i;
        }
    }
    for(int i = 0; i < K; ++i)
        WriteAdvice(st[i]);
    for(int i = 0; i < N; ++i)
        WriteAdvice(act[i]);
}

assistant

#include<bits/stdc++.h>
#include "assistant.h"
using namespace std;

void Assist(unsigned char *A, int N, int K, int R)
{
    int frq[100002];
    memset(frq, 0, sizeof(frq));
    int poz = 0;
    for(int i = 0; i < R; ++i)
    {
        if(A[i] == 1)
            ++poz;
        else
            ++frq[poz];
    }
    set<int>good;
    set<int>bad;
    for(int i = 0; i < K; ++i)
        if(A[i] == 1)
            good.insert(i);
        else
            bad.insert(i);
    for(int i = 0; i < N; ++i)
    {
        int req = GetRequest();
        if(bad.find(req) == bad.end() && good.find(req) == good.end())
        {
            PutBack(*bad.begin());
            bad.erase(bad.begin());
            if(A[i + K] == 1)
                good.insert(req);
            else
                bad.insert(req);
        }
        else
            if(bad.find(req) == bad.end())
            {
                good.erase(req);
                if(A[i + K] == 1)
                    good.insert(req);
                else
                    bad.insert(req);
            }
            else
            {
                bad.erase(req);
                if(A[i + K] == 1)
                    good.insert(req);
                else
                    bad.insert(req);
            }
    }
}

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