Submission #857730

#	Time	Username	Problem	Language	Result	Execution time	Memory
857730		Vanio	Speedrun (RMI21_speedrun)	C++17	48 / 100	83 ms	1528 KiB

speedrun

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

int n;
int f[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 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]);
        }
    }
}

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 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;}
        }
    }
}

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