Submission #587451

#	Time	Username	Problem	Language	Result	Execution time	Memory
587451		Deepesson	Speedrun (RMI21_speedrun)	C++17	100 / 100	125 ms	872 KiB

speedrun

#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,1);
    }
    for(int i=0;i!=10;++i){
        int x = (1<<i)&b;
        bool k = x;
        if(k)setHint(v+1,i+10+1,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+1))x+=1<<i;
    }
    return x;
}
int obternum2(void){
    int x=0;
    for(int i=0;i!=10;++i){
        if(getHint(i+10+1))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 (stderr)

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: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40