oj.uz

Submission #587448

# Submission time Handle Problem Language Result Execution time Memory
587448 2022-07-01T21:49:12 Z Deepesson Speedrun (RMI21_speedrun) C++17
0 / 100
 54 ms 676 KB 
#include <bits/stdc++.h>
#define MAX 1005
void assignHints(int subtask, int N, int A[], int B[]);
void speedrun(int subtask, int N, int start);

void setHintLen(int l);
void setHint(int i, int j, bool b);
int getLength();
bool getHint(int j);
bool goTo(int x);

void escreverinteiros(int v,int a,int b){
    for(int i=0;i!=10;++i){
        int x = (1<<i)&a;
        bool k = x;
        if(k)setHint(v+1,i,1);
    }
    for(int i=0;i!=10;++i){
        int x = (1<<i)&b;
        bool k = x;
        if(k)setHint(v+1,i+10,1);
    }
}

typedef std::pair<int,int> pii;
std::vector<int> con[MAX];
int inteiro2[MAX];
void explora(int pos,int prev,int deve=0){
    std::vector<int> toexp;
    for(auto&x:con[pos])if(x!=prev)toexp.push_back(x);
    if(!toexp.size()){
        inteiro2[pos]=deve;
        return;
    }
    inteiro2[pos]=toexp[0];
    for(int i=0;i!=toexp.size()-1;++i){
        explora(toexp[i],pos,toexp[i+1]);
    }
    explora(toexp.back(),pos,deve);
}
int inteiro1[MAX];
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    setHintLen(20);
   // printf("ta\n");

    for(int i=1;i!=N;++i){
     //   std::cout<<A[i]<<" "<<B[i]<<"\n";
        con[A[i]-1].push_back(B[i]-1);
        con[B[i]-1].push_back(A[i]-1);
    }
    //printf("show\n");
    ///Primeira etapa
    {
        std::queue<pii> queue;
        queue.push({0,0});
        bool ok[N]={};
        while(queue.size()){
            auto __ = queue.front();
            queue.pop();
            if(ok[__.first])continue;
            ok[__.first]=true;
            inteiro1[__.first]=__.second;
            for(auto&x:con[__.first]){
                queue.push({x,__.first});
            }
        }
    }
   // printf("Show\n");
    explora(0,-1);

    ///Etapa final: Escrever
    for(int i=0;i!=N;++i){
        //std::cout<<inteiro1[i]<<" "<<inteiro2[i]<<"\n";
        escreverinteiros(i,inteiro1[i],inteiro2[i]);
    }
}
int obternum1(void){
    int x=0;
    for(int i=0;i!=10;++i){
        if(getHint(i))x+=1<<i;
    }
    return x;
}
int obternum2(void){
    int x=0;
    for(int i=0;i!=10;++i){
        if(getHint(i+10))x+=1<<i;
    }
    return x;
}
void speedrun(int subtask, int N, int start) { /* your solution here */
    --start;
    ///Ir para o node oritinal
    bool foi[N]={};
  //  std::cout<<obternum1()<<" "<<obternum2()<<"\n";
    //std::cout<<obternum1()<<" "<<start<<"\n";
    foi[start]=true;
    int count=N-1;
    while(start!=obternum1()){
        start=obternum1();
        goTo(obternum1()+1);
      //  std::cout<<start<<" "<<obternum1()<<"\n";
        if(!foi[start]){
            foi[start]=true;
            --count;
        }
    }
    if(!count)return;
    std::vector<int> stk;
    stk.push_back(start);
    int prox=obternum2();
    while(stk.size()){
      //  std::cout<<"Explora "<<start<<" mira "<<prox<<"\n";
        if(goTo(prox+1)){
            stk.push_back(prox);
            start=prox;
            prox=obternum2();
        }else {
            stk.pop_back();
            start=stk.back();
            goTo(stk.back()+1);
        }
        if(!foi[start]){
            foi[start]=true;
            --count;
        }
        if(!count)break;
    }
}

Compilation message

speedrun.cpp: In function 'void explora(int, int, int)':
speedrun.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i!=toexp.size()-1;++i){
      |                 ~^~~~~~~~~~~~~~~~

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 360 KB Invalid bit index for setHint
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 676 KB Invalid bit index for getHint
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 464 KB Invalid bit index for setHint
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Invalid bit index for setHint
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Invalid bit index for setHint
2 Halted 0 ms 0 KB -