oj.uz

Submission #857729

# Submission time Handle Problem Language Result Execution time Memory
857729 2023-10-06T17:30:47 Z Vanio Speedrun (RMI21_speedrun) C++17
29 / 100
 3500 ms 2036 KB 
#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;
            pr=i;
            if(p!=pr){goTo(p); i=p;}
            else{goTo(q); 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;
            pr=i;
            if(p!=pr){goTo(p); i=p;}
            else{goTo(q); i=q;}
        }
    }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1288 KB Output is correct
2 Correct 27 ms 1524 KB Output is correct
3 Correct 26 ms 1540 KB Output is correct
4 Correct 20 ms 2036 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1204 KB Output is correct
2 Correct 50 ms 1216 KB Output is correct

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3518 ms 688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB setHintLen was never called
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB setHintLen was never called
2 Halted 0 ms 0 KB -