oj.uz

Submission #625033

# Submission time Handle Problem Language Result Execution time Memory
625033 2022-08-09T09:20:14 Z andrei_boaca Board (CEOI13_board) C++14
100 / 100
 198 ms 1036 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
auto START=chrono::steady_clock().now();
int mytime()
{
    auto END=chrono::steady_clock().now();
    int x=chrono::duration_cast<chrono::milliseconds> (END-START).count();
    return x;
}
int a,b;
string s;
int val[100005],lg;
vector<short> va,vb;
void multiply()
{
    int last=lg%2;
    if(last==1)
        val[lg++]=1;
    else
        val[lg-1]++;
}
void divide()
{
    int last=lg%2;
    if(val[lg-1]==1)
        lg--;
    else
        val[lg-1]--;
}
void add()
{
    int last=lg%2;
    if(last==0)
    {
        if(val[lg-1]>1)
        {
            val[lg-1]--;
            val[lg++]=1;
        }
        else
        {
            lg--;
            val[lg-1]++;
        }
        return;
    }
    else
    {
        int nr1=val[lg-1];
        int nr0=val[lg-2];
        lg-=2;
        if(nr0==1)
        {
            val[lg-1]++;
            val[lg++]=nr1;
        }
        else
        {
            nr0--;
            val[lg++]=nr0;
            val[lg++]=1;
            val[lg++]=nr1;
        }
    }
}
void subtract()
{
    int last=lg%2;
    if(last==1)
    {
        if(val[lg-1]==1)
        {
            lg--;
            val[lg-1]++;
        }
        else
        {
            val[lg-1]--;
            val[lg++]=1;
        }
        return;
    }
    else
    {
        int nr0=val[lg-1];
        int nr1=val[lg-2];
        lg-=2;
        if(nr1==1)
        {
            val[lg-1]++;
            val[lg++]=nr0;
        }
        else
        {
            nr1--;
            val[lg++]=nr1;
            val[lg++]=1;
            val[lg++]=nr0;
        }
    }
}
int getniv(int x)
{
    for(int d=0;d<=62;d++)
    {
        int st=(1<<d);
        int dr=st*2-1;
        if(x>=st&&x<=dr)
            return d;
    }
    return -1;
}
vector<int> dif;
void getdif()
{
    dif.clear();
    int t=0;
    for(int i=va.size()-1;i>=0;i--)
    {
        int x=va[i]-t-vb[i];
        t=0;
        if(x<0)
        {
            x+=2;
            t=1;
        }
        dif.push_back(x);
    }
    while(!dif.empty()&&dif.back()==0)
        dif.pop_back();
    if(dif.empty())
        dif.push_back(0);
    reverse(dif.begin(),dif.end());
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>s;
    lg=1;
    val[0]=1;
    for(int i=0;i<s.size();i++)
    {
        char c=s[i];
        if(c=='1')
            multiply();
        if(c=='2')
        {
            multiply();
            add();
        }
        if(c=='U')
            divide();
        if(c=='L')
            subtract();
        if(c=='R')
            add();
    }
    for(int i=0;i<lg;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);
        }
    }
    cin>>s;
    lg=1;
    val[0]=1;
    for(int i=0;i<s.size();i++)
    {
        char c=s[i];
        if(c=='1')
            multiply();
        if(c=='2')
        {
            multiply();
            add();
        }
        if(c=='U')
            divide();
        if(c=='L')
            subtract();
        if(c=='R')
            add();
    }
    for(int i=0;i<lg;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);
        }
    }
    int rez=0;
    int ans=1e9;
    if(va.size()<vb.size())
        swap(va,vb);
    while(va.size()>vb.size())
    {
        rez++;
        va.pop_back();
    }
    bool need=0;
    for(int i=0;i<va.size();i++)
        if(va[i]!=vb[i])
        {
            if(va[i]<vb[i])
                need=1;
            break;
        }
    if(need)
        swap(va,vb);
    /*for(int i:va)
        cout<<i;
    cout<<'\n';
    for(int i:vb)
        cout<<i;
    cout<<'\n';*/
    getdif();
    while(dif.size()>2)
    {
        dif.pop_back();
        va.pop_back();
        vb.pop_back();
        rez+=2;
    }
    while(dif.size())
    {
        if(mytime()>=199)
        {
            cout<<ans;
            return 0;
        }
        getdif();
        int x=0;
        for(int i:dif)
            x=x*2+i;
        ans=min(ans,x+rez);
        if(x==0)
            break;
        rez+=2;
        va.pop_back();
        vb.pop_back();
    }
    cout<<ans;
    return 0;
}

Compilation message

board.cpp: In function 'void divide()':
board.cpp:25:9: warning: unused variable 'last' [-Wunused-variable]
   25 |     int last=lg%2;
      |         ^~~~
board.cpp: In function 'int main()':
board.cpp:143:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
board.cpp:176:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
board.cpp:216:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |     for(int i=0;i<va.size();i++)
      |                 ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 73 ms 468 KB Output is correct
4 Correct 62 ms 340 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 28 ms 340 KB Output is correct
4 Correct 52 ms 340 KB Output is correct
5 Correct 2 ms 980 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 2 ms 1036 KB Output is correct
4 Correct 158 ms 496 KB Output is correct
5 Correct 162 ms 504 KB Output is correct
6 Correct 198 ms 980 KB Output is correct