Submission #624959

#	Time	Username	Problem	Language	Result	Execution time	Memory
624959		andrei_boaca	Board (CEOI13_board)	C++14	20 / 100	9 ms	2572 KiB

board

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll a,b,goodA,goodB;
string s;
vector<ll> val,va,vb;
void multiply()
{
    ll lg=val.size();
    int last=lg%2;
    if(last==1)
        val.push_back(1);
    else
        val[lg-1]++;
}
void divide()
{
    ll lg=val.size();
    int last=lg%2;
    if(val[lg-1]==1)
        val.pop_back();
    else
        val[lg-1]--;
}
void add()
{
    ll lg=val.size();
    int last=lg%2;
    if(last==0)
    {
        if(val[lg-1]>1)
        {
            val[lg-1]--;
            val.push_back(1);
        }
        else
        {
            assert(lg>=2);
            val.pop_back();
            lg--;
            val[lg-1]++;
        }
        return;
    }
    else
    {
        ll nr1=val[lg-1];
        ll nr0=val[lg-2];
        val.pop_back();
        val.pop_back();
        lg-=2;
        assert(nr0>0&&nr1>0);
        if(nr0==1)
        {
            val[lg-1]++;
            val.push_back(nr1);
        }
        else
        {
            nr0--;
            val.push_back(nr0);
            val.push_back(1);
            val.push_back(nr1);
        }
    }
}
void subtract()
{
    int lg=val.size();
    int last=lg%2;
    if(last==1)
    {
        if(val[lg-1]==1)
        {
            lg--;
            val.pop_back();
            val[lg-1]++;
        }
        else
        {
            val[lg-1]--;
            val.push_back(1);
        }
        return;
    }
    else
    {
        ll nr0=val[lg-1];
        ll nr1=val[lg-2];
        val.pop_back();
        val.pop_back();
        if(nr1==1)
        {
            val[lg-1]++;
            val.push_back(nr0);
        }
        else
        {
            nr1--;
            val.push_back(nr1);
            val.push_back(1);
            val.push_back(nr0);
        }
    }
}
ll getniv(ll x)
{
    for(ll d=0;d<=62;d++)
    {
        ll st=(1LL<<d);
        ll dr=st*2LL-1;
        if(x>=st&&x<=dr)
            return d;
    }
    return -1;
}
int main()
{
    cin>>s;
    val.push_back(1);
    goodA=1;
    ll x=1;
    for(char c:s)
    {
        if(c=='1')
        {
            multiply();
            goodA*=2LL;
            x*=2LL;
        }
        if(c=='2')
        {
            multiply();
            goodA*=2LL;
            x*=2LL;
            add();
            x++;
            goodA++;
        }
        if(c=='U')
        {
            divide();
            x/=2;
            goodA/=2;
        }
        if(c=='L')
        {
            //subtract();
            goodA--;
        }
        if(c=='R')
        {
            add();
            x++;
            goodA++;
        }
    }
    for(int i=0;i<val.size();i++)
    {
        if(i%2==0)
        {
            for(int j=1;j<=val[i];j++)
                va.push_back(1);
        }
        else
        {
            for(int j=1;j<=val[i];j++)
                va.push_back(0);
        }
    }
    val.clear();
    //val.shrink_to_fit();
    cin>>s;
    val.push_back(1);
    goodB=1;
    for(char c:s)
    {
        if(c=='1')
        {
            //multiply();
            goodB*=2LL;
        }
        if(c=='2')
        {
            //multiply();
            goodB*=2LL;
            //add();
            goodB++;
        }
        if(c=='U')
        {
            //divide();
            goodB/=2;
        }
        if(c=='L')
        {
            //subtract();
            goodB--;
        }
        if(c=='R')
        {
            //add();
            goodB++;
        }
    }
    for(int i=0;i<val.size();i++)
    {
        if(i%2==0)
        {
            for(int j=1;j<=val[i];j++)
                vb.push_back(1);
        }
        else
        {
            for(int j=1;j<=val[i];j++)
                vb.push_back(0);
        }
    }
    ll rez=0;
    ll ans=1e18;
    /*while(va.size()>50)
    {
        va.pop_back();
        rez++;
    }
    while(vb.size()>50)
    {
        vb.pop_back();
        rez++;
    }*/
    assert(va.size()<=51);
    ll a=0,b=0;
    for(int i:va)
    {
        a=a*2LL+i;
        //cout<<i;
    }
    /*for(int i:vb)
        b=b*2LL+i;*/
    assert(a==x);
    //assert(a==goodA&&b==goodB);
    a=goodA;
    b=goodB;
    if(a<b)
        swap(a,b);
    ll nivA=getniv(a),nivB=getniv(b);
    while(nivA>nivB)
    {
        nivA--;
        rez++;
        a/=2;
    }
    while(nivA>=0)
    {
        ans=min(ans,rez+abs(a-b));
        rez+=2;
        a/=2;
        b/=2;
        nivA--;
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

board.cpp: In function 'void divide()':
board.cpp:20:9: warning: unused variable 'last' [-Wunused-variable]
   20 |     int last=lg%2;
      |         ^~~~
board.cpp: In function 'int main()':
board.cpp:159:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for(int i=0;i<val.size();i++)
      |                 ~^~~~~~~~~~~
board.cpp:207:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |     for(int i=0;i<val.size();i++)
      |                 ~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10