Submission #5923

#	Time	Username	Problem	Language	Result	Execution time	Memory
5923		baneling100	Board (CEOI13_board)	C++98	100 / 100	0 ms	2456 KiB

board

#include <stdio.h>
#include <string.h>
 
int xlen, ylen, a[100001], atop, b[100001], btop, c[100001], ctop, ans;
char x[100002], y[100002];
 
void input(void)
{
    scanf("%s %s",&x[1],&y[1]);
    xlen=strlen(&x[1]);
    ylen=strlen(&y[1]);
}
 
int big(void)
{
    int i;
 
    for(i=1 ; i<=atop ; i++)
    {
        if(a[i]>b[i])
            return 1;
        else if(a[i]<b[i])
            return -1;
    }
    return 0;
}
 
void process(void)
{
    int i, temp;
 
    for(i=1 ; i<=xlen ; i++)
    {
        if(x[i]=='1')
            a[++atop]=0;
        else if(x[i]=='2')
            a[++atop]=1;
        else if(x[i]=='U')
        {
            if(a[atop]<0)
                a[atop-1]-=(1-a[atop])/2;
            else
                a[atop-1]+=a[atop]/2;
            atop--;
        }
        else if(x[i]=='L')
            a[atop]--;
        else
            a[atop]++;
    }
    for(i=1 ; i<=ylen ; i++)
    {
        if(y[i]=='1')
            b[++btop]=0;
        else if(y[i]=='2')
            b[++btop]=1;
        else if(y[i]=='U')
        {
            if(b[btop]<0)
                b[btop-1]-=(1-b[btop])/2;
            else
                b[btop-1]+=b[btop]/2;
            btop--;
        }
        else if(y[i]=='L')
            b[btop]--;
        else
            b[btop]++;
    }
    for(i=atop ; i>=1 ; i--)
    {
        if(a[i]<0)
        {
            a[i-1]-=(1-a[i])/2;
            a[i]=(-a[i])%2;
        }
        else
        {
            a[i-1]+=a[i]/2;
            a[i]%=2;
        }
    }
    for(i=btop ; i>=1 ; i--)
    {
        if(b[i]<0)
        {
            b[i-1]-=(1-b[i])/2;
            b[i]=(-b[i])%2;
        }
        else
        {
            b[i-1]+=b[i]/2;
            b[i]%=2;
        }
    }
    if(atop>btop)
    {
        ans+=atop-btop;
        atop=btop;
    }
    else
    {
        ans+=btop-atop;
        btop=atop;
    }
    temp=big();
    ctop=atop;
    if(temp==1)
    {
        for(i=ctop ; i>=1 ; i--)
        {
            c[i]+=a[i]-b[i];
            if(c[i]<0)
            {
                c[i-1]-=(1-c[i])/2;
                c[i]=(-c[i])%2;
            }
            else
            {
                c[i-1]+=c[i]/2;
                c[i]%=2;
            }
        }
        for(i=1 ; i<=ctop ; i++)
            if(c[i])
            {
                temp=i;
                break;
            }
        while(ctop-temp>=2)
        {
            ans+=2;
            if(a[ctop]==0 && b[ctop]==1)
            {
                c[ctop-1]++;
                if(temp>ctop-1)
                    temp=ctop-1;
                for(i=ctop-1 ; i>=1 ; i--)
                {
                    if(c[i]>1)
                    {
                        c[i-1]++;
                        if(temp>i-1)
                            temp=i-1;
                        c[i]-=2;
                    }
                    else
                        break;
                }
            }
            ctop--;
        }
        if(c[ctop-1])
            ans+=2;
        if(c[ctop])
            ans++;
    }
    else if(temp==-1)
    {
        for(i=ctop ; i>=1 ; i--)
        {
            c[i]+=b[i]-a[i];
            if(c[i]<0)
            {
                c[i-1]-=(1-c[i])/2;
                c[i]=(-c[i])%2;
            }
            else
            {
                c[i-1]+=c[i]/2;
                c[i]%=2;
            }
        }
        for(i=1 ; i<=ctop ; i++)
            if(c[i])
            {
                temp=i;
                break;
            }
        while(ctop-temp>=2)
        {
            ans+=2;
            if(a[ctop]==1 && b[ctop]==0)
            {
                c[ctop-1]++;
                if(temp>ctop-1)
                    temp=ctop-1;
                for(i=ctop-1 ; i>=1 ; i--)
                {
                    if(c[i]>1)
                    {
                        c[i-1]++;
                        if(temp>i-1)
                            temp=i-1;
                        c[i]-=2;
                    }
                    else
                        break;
                }
            }
            ctop--;
        }
        if(c[ctop-1])
            ans+=2;
        if(c[ctop])
            ans++;
    }
}
 
void output(void)
{
    printf("%d",ans);
}
 
int main(void)
{
    input();
    process();
    output();
 
    return 0;
}

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