oj.uz

Submission #430398

# Submission time Handle Problem Language Result Execution time Memory
430398 2021-06-16T13:21:41 Z JeanBombeur Last supper (IOI12_supper) C++17
100 / 100
 160 ms 11240 KB 
#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;
}

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2924 KB Output is correct
2 Correct 2 ms 2924 KB Output is correct
3 Correct 4 ms 2928 KB Output is correct
4 Correct 5 ms 3068 KB Output is correct
5 Correct 7 ms 3340 KB Output is correct
6 Correct 7 ms 3340 KB Output is correct
7 Correct 6 ms 3468 KB Output is correct
8 Correct 7 ms 3340 KB Output is correct
9 Correct 7 ms 3340 KB Output is correct
10 Correct 8 ms 3468 KB Output is correct
11 Correct 9 ms 3364 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3784 KB Output is correct
2 Correct 47 ms 6836 KB Output is correct
3 Correct 103 ms 10416 KB Output is correct
4 Correct 119 ms 9476 KB Output is correct
5 Correct 113 ms 9652 KB Output is correct
6 Correct 109 ms 10028 KB Output is correct
7 Correct 153 ms 10320 KB Output is correct
8 Correct 84 ms 8968 KB Output is correct
9 Correct 86 ms 10148 KB Output is correct
10 Correct 131 ms 10720 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 8836 KB Output is correct
2 Correct 126 ms 10436 KB Output is correct
3 Correct 144 ms 10448 KB Output is correct
4 Correct 132 ms 10548 KB Output is correct
5 Correct 157 ms 10676 KB Output is correct
6 Correct 121 ms 10592 KB Output is correct
7 Correct 121 ms 10472 KB Output is correct
8 Correct 112 ms 10096 KB Output is correct
9 Correct 110 ms 11240 KB Output is correct
10 Correct 130 ms 10420 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3336 KB Output is correct
2 Correct 7 ms 3340 KB Output is correct
3 Correct 7 ms 3340 KB Output is correct
4 Correct 7 ms 3336 KB Output is correct
5 Correct 8 ms 3340 KB Output is correct
6 Correct 7 ms 3340 KB Output is correct
7 Correct 10 ms 3340 KB Output is correct
8 Correct 7 ms 3340 KB Output is correct
9 Correct 7 ms 3336 KB Output is correct
10 Correct 7 ms 3488 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 10160 KB Output is correct - 120000 bits used
2 Correct 120 ms 10448 KB Output is correct - 122000 bits used
3 Correct 133 ms 10356 KB Output is correct - 125000 bits used
4 Correct 158 ms 10380 KB Output is correct - 125000 bits used
5 Correct 145 ms 10452 KB Output is correct - 125000 bits used
6 Correct 105 ms 10400 KB Output is correct - 125000 bits used
7 Correct 123 ms 10496 KB Output is correct - 124828 bits used
8 Correct 160 ms 10380 KB Output is correct - 124910 bits used
9 Correct 155 ms 10392 KB Output is correct - 125000 bits used
10 Correct 129 ms 10192 KB Output is correct - 125000 bits used