Submission #1297257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297257		denislav	cmp (balkan11_cmp)	C++20	100 / 100	2116 ms	96156 KiB

cmp

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
# include "cmp.h"

int delta[11];

void prepare()
{
    delta[0]=1;
    int p=1;
    for(int i=1;i<=5;i++)
    {
        p*=4;
        delta[i]=delta[i-1]+p;
    }
}

vector<int> to4(int n)
{
    vector<int> ans;
    for(int i=0;i<6;i++)
    {
        ans.push_back(n%4);
        n/=4;
    }
    reverse(ans.begin(),ans.end());
    return ans;
}

void remember(int n)
{
    prepare();

    vector<int> v=to4(n);
    int x=0;
    for(int i=0;i<6;i++)
    {
        x*=4;
        x+=v[i];
        bit_set(delta[i]+x);
        //cout<<i<<":"<<delta[i]+x<<"\n";
    }
}

int compare(int n)
{
    prepare();
    vector<int> v=to4(n);

    int l=0,r=5,ans=-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        int x=0;
        for(int i=0;i<=mid;i++)
        {
            x*=4;
            x+=v[i];
        }
        if(bit_get(delta[mid]+x)==1)
        {
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;

        //cout<<mid<<"::"<<delta[mid]+x<<"\n";
    }

    if(ans==5) return 0;
    ans++;

    if(v[ans]==0) return -1;
    else if(v[ans]==3) return 1;
    else if(v[ans]==1)
    {
        int x=0;
        for(int i=0;i<ans;i++)
        {
            x*=4;
            x+=v[i];
        }
        x*=4;
        if(bit_get(delta[ans]+x)) return 1;
        else return -1;
    }
    else if(v[ans]==2)
    {
        int x=0;
        for(int i=0;i<ans;i++)
        {
            x*=4;
            x+=v[i];
        }
        x*=4;
        x+=3;

        if(bit_get(delta[ans]+x)) return -1;
        else return 1;
    }
}

Compilation message (stderr)

cmp.cpp: In function 'int compare(int)':
cmp.cpp:103:1: warning: control reaches end of non-void function [-Wreturn-type]
  103 | }
      | ^

• Subtask 1: 100 / 100