Submission #430168

#	Time	Username	Problem	Language	Result	Execution time	Memory
430168		JeanBombeur	Last supper (IOI12_supper)	C++17	34 / 100	502 ms	20356 KiB

advisor

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

//   <|°_°|>

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

int Id[MAX_COULEURS];

int CouleursPresentes[MAX_COULEURS];

vector <int> Dates[MAX_COULEURS];

priority_queue <pair <int, int>> Echafaud;

void ComputeAdvice(int *Couleurs, int nbCouleurs, int tailleEchafaud, int nbBits) {
    
    nbBits ++;
    
    for (int i = 0; i < nbCouleurs; i ++)
    {
        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 ++)
    {
        CouleursPresentes[i] = i;
        Id[i] = i + 1;
        Echafaud.push({Dates[i].back(), i});
    }
    
    int logMax = 0;
    while ((1 << logMax) <= tailleEchafaud)
        logMax ++;
    
    for (int i = 0; i < nbCouleurs; i ++)
    {
        Dates[Couleurs[i]].pop_back();
        int mask = (1 << logMax) - 1;
        if (Id[Couleurs[i]] == 0)
        {
            mask = Echafaud.top().second;
            Id[Couleurs[i]] = mask + 1;
            Id[CouleursPresentes[mask]] = 0;
            CouleursPresentes[mask] = Couleurs[i];
            Echafaud.pop();
        }
        Echafaud.push({Dates[Couleurs[i]].back(), Id[Couleurs[i]] - 1});
        for (int k = 0; k < logMax; k ++)
        {
            WriteAdvice((mask & 1));
            mask >>= 1;
        }
    }
    printf("\n");
    return;
}

assistant

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

//   <|°_°|>

const int NB_COULEURS = (100 * 1000);

int EchafaudActuel[NB_COULEURS];

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

    longueur ++;

    int logMax = 0;
    while ((1 << logMax) <= tailleEchafaud)
        logMax ++;
        
    for (int i = 0; i < tailleEchafaud; i ++)
    {
        EchafaudActuel[i] = i;
    }
    
    int curBit = 0;
    
    for (int i = 0; i < nbCouleurs; i ++)
    {
        int mask = 0;
        for (int k = curBit + logMax - 1; k >= curBit; k --)
        {
            mask <<= 1;
            mask |= (int)Advice[k];
        }
        curBit += logMax;
        int id = GetRequest();
        if (mask < (1 << logMax) - 1)
        {
            PutBack(EchafaudActuel[mask]);
            EchafaudActuel[mask] = id;
        }
    }
    return;
}

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