oj.uz

Submission #858164

# Submission time Handle Problem Language Result Execution time Memory
858164 2023-10-07T14:16:14 Z Vanio Speedrun (RMI21_speedrun) C++17
60 / 100
 124 ms 1788 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1448 KB Output is correct
2 Correct 24 ms 1452 KB Output is correct
3 Correct 20 ms 1324 KB Output is correct
4 Correct 27 ms 1292 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1712 KB Output is correct
2 Correct 53 ms 1468 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 1208 KB Output is correct
2 Correct 82 ms 1196 KB Output is correct
3 Correct 82 ms 1212 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 1452 KB Output is correct
2 Correct 90 ms 1620 KB Output is correct
3 Correct 124 ms 1276 KB Output is correct
4 Correct 83 ms 1616 KB Output is correct
5 Correct 97 ms 1788 KB Output is correct
6 Correct 57 ms 1548 KB Output is correct

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 -