oj.uz

Submission #5923

# Submission time Handle Problem Language Result Execution time Memory
5923 2014-05-23T10:39:40 Z baneling100 Board (CEOI13_board) C++
100 / 100
 0 ms 2456 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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