oj.uz

Submission #579739

# Submission time Handle Problem Language Result Execution time Memory
579739 2022-06-19T17:42:48 Z Deepesson Last supper (IOI12_supper) C++17
100 / 100
 381 ms 83836 KB 
#include <bits/stdc++.h>

void WriteAdvice(unsigned char a);
#define MAX 505000
bool conselho[MAX];
int local[MAX],menciona[MAX];
typedef std::pair<int,int> pii;
void ComputeAdvice(int *C, int N, int K, int M) {
   // std::cout<<"Show"<<std::endl;
    std::map<int,std::deque<int>> mapa;
    for(int i=0;i!=N;++i){
        mapa[C[i]].push_back(i);
    }
    for(auto&x:local)x=-1;
    std::priority_queue<pii> queue;
    for(int i=0;i!=K;++i){
        int x=1e9;
        if(mapa[i].size())x=mapa[i].front();
        queue.push({x,i});
        local[i]=x;
        menciona[i]=i;
    }
   // std::cout<<"blz"<<std::endl;
    ///Menciona -> Guarda a cordenada da instrucao q menciona
    ///Local -> Diz o proximo valor da queue
    for(int i=0;i!=N;++i){
        int quer = C[i];
        ///A cor esta no andaime
        if(local[quer]!=-1){
            ///Registra que tem que manter a cor do cara anterior
            conselho[menciona[quer]]=1;
            ///Anda com a cor atual
            mapa[quer].pop_front();
            ///Pega a proxima cor atual
            int x=1e9;
            if(mapa[quer].size())x=mapa[quer].front();
            ///Joga na queue
            queue.push({x,quer});
            ///Atualiza o local
            local[quer]=x;
            ///Gera a cord
            menciona[quer]=i+K;
            continue;
        }

        ///Procurar cor mais distante
        int cord = -1;
        while(queue.size()){
            auto __ = queue.top();
            queue.pop();
            if(__.first!=local[__.second])continue;
            cord=__.second;
            break;
        }

        ///Anda com a cor atual
        mapa[quer].pop_front();
        ///Pega a proxima cor atual
        int x=1e9;
        if(mapa[quer].size())x=mapa[quer].front();
        ///Joga na queue
        queue.push({x,quer});
        ///Atualiza o local
        local[quer]=x;
        ///Zera a cord (nao existe mais)
        local[cord]=-1;
        ///Gera a cord
        menciona[quer]=i+K;
    }
   // std::cout<<"Ok envia:"<<std::endl;
    for(int i=0;i!=N+K;++i){
           // std::cout<<" "<<conselho[i]<<" ";
        WriteAdvice(conselho[i]);
    }
   // std::cout<<std::endl;
}
#include <bits/stdc++.h>

int GetRequest();
void PutBack(int T);

void Assist(unsigned char *A, int N, int K, int R) {
    std::map<int,int> paleta;
    std::vector<int> lixo;
    for(int i=0;i!=K;++i){
        paleta[i]=1;
        if(!A[i])lixo.push_back(i);
    }
 //   std::cout<<"Ok recebe:"<<std::endl;
    for(int i=0;i!=N+K;++i){
          //  std::cout<<" "<<(int)A[i]<<" ";
    }
   // std::cout<<std::endl;
    for(int i=0;i!=N;++i){
        int x = GetRequest();
        //std::cout<<"Recebe "<<x<<" "<<(int)A[i+K]<<std::endl;
        if(paleta[x]){
           // std::cout<<"Ja tem :)"<<std::endl;
            if(!(A[i+K])){
                lixo.push_back(x);
            }
        }else {
            int b = lixo.back();
            lixo.pop_back();
            PutBack(b);
            paleta[b]=0;
            if(A[i+K])
            paleta[x]=1;
            else lixo.push_back(x);
        }
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2572 KB Output is correct
2 Correct 1 ms 2568 KB Output is correct
3 Correct 4 ms 3720 KB Output is correct
4 Correct 4 ms 2728 KB Output is correct
5 Correct 10 ms 5196 KB Output is correct
6 Correct 8 ms 5328 KB Output is correct
7 Correct 8 ms 3672 KB Output is correct
8 Correct 12 ms 6592 KB Output is correct
9 Correct 13 ms 5448 KB Output is correct
10 Correct 12 ms 5828 KB Output is correct
11 Correct 11 ms 5572 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8400 KB Output is correct
2 Correct 83 ms 17888 KB Output is correct
3 Correct 381 ms 75400 KB Output is correct
4 Correct 265 ms 55292 KB Output is correct
5 Correct 300 ms 55408 KB Output is correct
6 Correct 271 ms 56544 KB Output is correct
7 Correct 277 ms 61068 KB Output is correct
8 Correct 287 ms 71760 KB Output is correct
9 Correct 119 ms 11000 KB Output is correct
10 Correct 300 ms 63972 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 49632 KB Output is correct
2 Correct 340 ms 62320 KB Output is correct
3 Correct 315 ms 62664 KB Output is correct
4 Correct 315 ms 59028 KB Output is correct
5 Correct 227 ms 44992 KB Output is correct
6 Correct 312 ms 62608 KB Output is correct
7 Correct 291 ms 60892 KB Output is correct
8 Correct 372 ms 83836 KB Output is correct
9 Correct 216 ms 41956 KB Output is correct
10 Correct 306 ms 62776 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5032 KB Output is correct
2 Correct 12 ms 6600 KB Output is correct
3 Correct 7 ms 3532 KB Output is correct
4 Correct 8 ms 5168 KB Output is correct
5 Correct 9 ms 5280 KB Output is correct
6 Correct 9 ms 5316 KB Output is correct
7 Correct 9 ms 5528 KB Output is correct
8 Correct 10 ms 5572 KB Output is correct
9 Correct 10 ms 5572 KB Output is correct
10 Correct 11 ms 6344 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 60156 KB Output is correct - 120000 bits used
2 Correct 300 ms 60840 KB Output is correct - 122000 bits used
3 Correct 328 ms 61472 KB Output is correct - 125000 bits used
4 Correct 293 ms 61608 KB Output is correct - 125000 bits used
5 Correct 317 ms 61524 KB Output is correct - 125000 bits used
6 Correct 294 ms 61516 KB Output is correct - 125000 bits used
7 Correct 331 ms 61508 KB Output is correct - 124828 bits used
8 Correct 364 ms 61624 KB Output is correct - 124910 bits used
9 Correct 296 ms 61552 KB Output is correct - 125000 bits used
10 Correct 379 ms 81456 KB Output is correct - 125000 bits used