Submission #430398

#	Time	Username	Problem	Language	Result	Execution time	Memory
430398		JeanBombeur	Last supper (IOI12_supper)	C++17	100 / 100	160 ms	11240 KiB

advisor

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include "advisor.h"
using namespace std;

//   <|°_°|>

const int INFINI = (1000 * 1000 * 1000);
const int MAX_COULEURS = (100 * 1000);

vector <int> Dates[MAX_COULEURS];
int Last[MAX_COULEURS];

bool IsIn[MAX_COULEURS];

priority_queue <pair <int, int>> APush;

bool KeepStart[MAX_COULEURS];
bool Keep[MAX_COULEURS];

void ComputeAdvice(int *Couleurs, int nbCouleurs, int tailleEchafaud, int nbBits) {

    nbBits ++;
    
    for (int i = 0; i < nbCouleurs; i ++)
    {
        Last[i] = -1;
        Dates[i].push_back(INFINI);
    }
    for (int i = nbCouleurs - 1; i >= 0; i --)
    {
        Dates[Couleurs[i]].push_back(i);
    }
    for (int i = 0; i < tailleEchafaud; i ++)
    {
        IsIn[i] = true;
        APush.push({Dates[i].back(), i});
    }
    
    for (int i = 0; i < nbCouleurs; i ++)
    {
        Dates[Couleurs[i]].pop_back();
        if (Couleurs[i] < tailleEchafaud && Last[Couleurs[i]] < 0)
        {
            KeepStart[Couleurs[i]] = IsIn[Couleurs[i]];
        }
        if (Last[Couleurs[i]] >= 0)
        {
            Keep[Last[Couleurs[i]]] = IsIn[Couleurs[i]];
        }
        Last[Couleurs[i]] = i;
        if (!IsIn[Couleurs[i]])
        {
            int id = APush.top().second;
            APush.pop();
            IsIn[id] = false;
            IsIn[Couleurs[i]] = true;
        }
        APush.push({Dates[Couleurs[i]].back(), Couleurs[i]});
    }
    for (int i = 0; i < tailleEchafaud; i ++)
    {
        WriteAdvice(KeepStart[i]);
    }
    for (int i = 0; i < nbCouleurs; i ++)
    {
        WriteAdvice(Keep[i]);
    }
    return;
}

assistant

#include <iostream>
#include <cstdio>
#include "assistant.h"
using namespace std;

//   <|°_°|>

const int NB_COULEURS = (100 * 1000);

bool IsOn[NB_COULEURS];

int ToPush[NB_COULEURS];
int fin = 0;

void Assist(unsigned char *Advice, int nbCouleurs, int tailleEchafaud, int nbBits) {

    nbBits ++;
    
    for (int i = 0; i < tailleEchafaud; i ++)
    {
        if (!Advice[i])
            ToPush[fin ++] = i;
        IsOn[i] = true;
    }
    
    for (int i = 0; i < nbCouleurs; i ++)
    {
        int id = GetRequest();
        if (!IsOn[id])
        {
            IsOn[id] = true;
            IsOn[ToPush[-- fin]] = false;
            PutBack(ToPush[fin]);
        }
        if (!Advice[i + tailleEchafaud])
            ToPush[fin ++] = id;
    }
    return;
}

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