Submission #12058

#	Time	Username	Problem	Language	Result	Execution time	Memory
12058		woqja125	Sequence (BOI14_sequence)	C++98	100 / 100	72 ms	1600 KiB

sequence

#include<stdio.h>
int d[100001];
long long getAns(int d[], int n, int dep)
{
	int i, start;
	int *arg;
	long long ans = 10234567890000000ll;
	if(n==1 || dep > 6)
	{
		for(i=2; i<=n; i++)d[1] |= d[i];
		if(d[1] == 1) return 10;
		if(d[1] %2 == 1)
		{
			for(i=1; i<=9; i++) if((d[1] >> i)%2 == 1)
			{
				ans = i*10;
				break;
			}
			for(i++; i<=9; i++) if((d[1] >> i)%2 == 1) ans = ans*10 + i;
			return ans;	
		}
		else
		{
			ans = 0;
			for(i=1; i<=9; i++) if((d[1] >> i)%2 == 1) ans = ans*10 + i;
			return ans;
		}
	}
	arg = new int[n/10+50];
	int fd = 0, N = 1;
	arg[1] = 0;
	for(i=1; i<=n; i++)
	{
		if(fd == 10)
		{
			arg[++N] = 0;
			fd = 0;
		}
		if(i == 1)
		{
			if(d[i] != 0) break;
		}
		else
		{
			if( (d[i] & (~(1<<fd))) != 0 ) break;
		}
		fd++;
	}
	if(i==n+1) return 0;
	for(start = 0; start<=9; start++)
	{
		fd = start;
		arg[N=1] = 0;
		for(i=1; i<=n; i++)
		{
			if(fd == 10)
			{
				arg[++N] = 0;
				fd = 0;
			}
			arg[N] |= d[i]&(~(1<<fd));
			fd++;
		}
		for(i=1; i<=N; i++) if(arg[i] != 0) break;
		if(i==N+1)
		{
			if(start != 0) { if(ans > start) ans = start; }
			else if(ans > 10) ans = 10;
		}
		else
		{
			long long l;
			if(start == 0) l = getAns(arg, N, dep+1);
			else l = getAns(arg, N, dep+1);
			if(ans > l*10 + start) ans = l*10 + start;
		}
	}
	delete[] arg;
	return ans;
}
int main()
{
	int n, i;
	scanf("%d", &n);
	for(i=1; i<=n; i++)
	{
		scanf("%d", d+i);
		d[i] = 1<<d[i];
	}
	printf("%lld", getAns(d, n, 1));
	return 0;
}

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