Submission #858164

#	Time	Username	Problem	Language	Result	Execution time	Memory
858164		Vanio	Speedrun (RMI21_speedrun)	C++17	60 / 100	124 ms	1788 KiB

speedrun

#include<bits/stdc++.h>
#include "speedrun.h"
using namespace std;

int n;
int f[1001];
vector<int> v[1001];

void seth(int p, int q){
    int j=f[p]*10+1;
    while(q>0){
        setHint(p,j,q%2);
        q/=2;
        j++;
    }
    if(!f[p]) f[p]=1;
}

void sethi(int k){
    int i,t,j;
    for(i=0;i<v[k].size();i++){
        t=v[k][i];
        j=i*10+1;
        while(t>0){
            setHint(k,j,t%2);
            t/=2;
            j++;
        }
    }
    t=v[k].size();
    j=311;
    while(t>0){
        setHint(k,j,t%2);
        t/=2;
        j++;
    }
}

void assignHints(int subtask, int N, int a[], int b[]){
    n=N;

    if(subtask==1){
        int i;
        setHintLen(n);
        for(i=1;i<n;i++){
            setHint(a[i],b[i],1);
            setHint(b[i],a[i],1);
        }
    }

    if(subtask==2){
        int c;
        if(a[2]==a[1] || a[2]==b[1]) c=a[2];
        else c=b[2];

        int l=1,h[20];
        while(c>0){
            h[l]=c%2;
            c/=2;
            l++;
        }
        setHintLen(l-1);
        int i,j;
        for(i=1;i<=n;i++){
            if(i==c) continue;
            for(j=1;j<l;j++) setHint(i,j,h[j]);
        }
    }

    if(subtask==3){
        int i;
        setHintLen(20);
        for(i=1;i<n;i++){
            seth(a[i],b[i]);
            seth(b[i],a[i]);
        }
    }

    if(subtask==4){
        int i;
        setHintLen(316);
        for(i=1;i<n;i++){
            v[a[i]].push_back(b[i]);
            v[b[i]].push_back(a[i]);
        }
        for(i=1;i<=n;i++){
            if(v[i].size()>31) setHint(i,316,1);
            else sethi(i);
        }
    }
}

void rec(int k, int p){
    int i;
    f[k]=1;
    for(i=1;i<=n;i++){
        if(getHint(i) && !f[i]){
            goTo(i);
            rec(i,k);
        }
    }
    if(p==0) return;
    goTo(p);
}

int getv(int indx){
    int s=0,t=512,i;
    for(i=indx;i>indx-10;i--){
        s+=getHint(i)*t;
        t/=2;
    }
    return s;
}

void dfs(int k, int prev){
    int br=0,t=16,i,j,s;
    f[k]=1;
    if(getHint(316)==0){
        for(i=315;i>310;i--){
            br+=t*getHint(i);
            t/=2;
        }
        for(i=1;i<=br;i++){
            s=0;
            t=512;
            for(j=i*10;j>(i-1)*10;j--){
                s+=t*getHint(j);
                t/=2;
            }
            if(f[s]==0){goTo(s); dfs(s,k);}
        }
    }
    else{
        for(i=1;i<=n;i++){
            if(f[i]==0){
                if(goTo(i)) dfs(i,k);
            }
        }
    }
    if(prev==0) return;
    goTo(prev);
}

void speedrun(int subtask, int N, int start){
    n=N;

    if(subtask==1) rec(start,0);

    if(subtask==2){
        int i,F=0,c=0,t=1;
        int l = getLength();
        for(i=1;i<=l;i++) if(getHint(i)==1){F=1; break;}
        if(F){
            for(i=1;i<l;i++) t*=2;
            for(i=l;i>=1;i--){
                c+=getHint(i)*t;
                t/=2;
            }
            goTo(c);
        }
        else c=start;
        for(i=1;i<=n;i++){
            if(i==c) continue;
            goTo(i);
            goTo(c);
        }
    }

    if(subtask==3){
        int pr=0,i=start;
        int p,q;
        while(1){
            p=getv(10);
            q=getv(20);
            if(p==0 || q==0) break;
            if(p!=pr){goTo(p); pr=i; i=p;}
            else{goTo(q); pr=i; i=q;}
        }
        if(pr!=0){
            goTo(pr);
            swap(i,pr);
        }
        else{
            p=getv(10);
            q=getv(20);
            pr=i;
            if(p!=0){goTo(p); i=p;}
            else{goTo(q); i=q;}
        }
        while(1){
            p=getv(10);
            q=getv(20);
            if(p==0 || q==0) break;
            if(p!=pr){goTo(p); pr=i; i=p;}
            else{goTo(q); pr=i; i=q;}
        }
    }

    if(subtask==4) dfs(start,0);
}

Compilation message (stderr)

speedrun.cpp: In function 'void sethi(int)':
speedrun.cpp:21:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(i=0;i<v[k].size();i++){
      |             ~^~~~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 0 / 40