Submission #11200

#	Time	Username	Problem	Language	Result	Execution time	Memory
11200		woqja125	Sequence (BOI14_sequence)	C++98	0 / 100	32 ms	6084 KiB

sequence

#include<stdio.h>
int d[100001];
long long getAns(int data[], const int n, int depth, bool prevZero)
{
	//printf("%d %d %d \n", n, data[1], data[2]);
    int *arg;
    long long ans = 102345678900000000ll;
    int i;
    for(i=1; i<=n; i++) if(data[i] != 0) break;
    if(i==n+1 && !prevZero) return 0;
    if(n==1 || depth > 6)
    {
        for(i=2; i<=n; i++) data[1] |= data[i];
        ans = 0;
        int c = 0;
        if(data[1] == 0 && prevZero)
        {
        	return 1;
        }
        else if(data[1] == 0)
        {
        	return 0;
        }
        if(data[1] % 2 == 1)
        {
            if(data[1] == 1) return 10;
            else
            {
                int i;
                for(i=1; i<=9; i++)
                {
                    if(((data[1] >> i) & 1) == 1)
                    {
                        ans = i*10;
                        break;
                    }
                }
                for(i++; i<=9; i++) if(((data[1] >> i) & 1) == 1) ans = ans * 10 + i;
                return ans;
            }
        }
        else
        {
            for(int i=1; i<=9; i++) if(((data[1] >> i) & 1) == 1) ans = ans * 10 + i;
            return ans;
        }
    }
    arg = new int[n/10+100];
    int start = 0;
    for(start = 0; start<=9; start++)
    {
        int fd, N;
        fd = start;
        arg[N = 1] = 0;
        for(int i=1; i<=n; i++)
        {
            if(fd == 10)
            {
                fd = 0;
                arg[++N] = 0;
            }
            arg[N] = arg[N] | (data[i] & (~(1<<fd)) );
            fd++;
        }

        long long l;
        //printf("Call %d %d %d %d %d\n", N, depth+1, arg[1], arg[2], start);
        for(i=1; i<=N; i++) if(arg[i] != 0) break;
        if(i==N+1 && start == 0 && !prevZero) return 0;
        else if(start == 0) l = getAns(arg, N, depth + 1, true);
        else l = getAns(arg, N, depth+1, false);
        //printf("Log %d %d %d %d %lld %d\n", N, depth+1, arg[1], arg[2], l, start);
        if(ans > l*10 + start)
        {
            ans = l*10 + start;
            //printf("Ans %lld\n", ans);
        }
    }
    delete[] arg;
    return ans;
}
int main()
{
    int n, i;
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%d", d+i);
    }
    for(i=1; i<=n; i++)
    {
        d[i] = 1<<d[i];
    }
    long long ans = getAns(d, n, 1, true);
    printf("%lld", ans);
    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 33
• Subtask 3: 0 / 25
• Subtask 4: 0 / 33