oj.uz

Submission #11110

# Submission time Handle Problem Language Result Execution time Memory
11110 2014-11-13T16:58:15 Z ainta Sequence (BOI14_sequence) C++
25 / 100
 376 ms 2148 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
long long Res = 99999999999999999LL;
void Do(int Num, vector<int>w, int p, int ck){
	int i, n = w.size(), j;
	if (p > 1000000)return;
	if (n == 1){
		if (ck){
			if (w[0] == 0)Res = min(Res, (long long)Num);
			return;
		}
		int tt;
		long long S = Num, P = p;
		if (w[0] & 1){
			for (i = 1; i<10; i++){
				if ((1 << i)&w[0])break;
			}
			tt = i;
			if (tt == 10){
				S += P * 10;
			}
			else{
				for (i = 9; i >= 1; i--){
					if ((1 << i)&w[0]){
						if (tt == i)P *= 10;
						S += P*i;
						P *= 10;
					}
				}
			}
		}
		else{
			for (i = 9; i >= 0; i--){
				if ((1 << i)&w[0]){
					S += P*i;
					P *= 10;
				}
			}
		}
		if (S * 10 < p) S += p;
		Res = min(Res, S);
		return;
	}
	vector<int>R((n - 1) / 10 + 1);
	if (Num * 10 > p){
		for (j = 0; j < n; j++){
			if (j)R[j / 10] |= w[j] & ~(1 << (j % 10));
			else R[j / 10] |= w[j];
		}
		Do(Num, R, -1, 1);
	}
	if (ck)return;
	for (i = 0; i < 10; i++){
		vector<int>R((n - 1 + i) / 10 + 1);
		for (j = 0; j < n; j++){
			R[(i + j) / 10] |= w[j] & ~(1 << ((i + j) % 10));
		}
		Do(Num + i*p, R, p * 10, 0);
	}
}
int main()
{
	int i, n;
	scanf("%d", &n);
	vector<int>L(n);
	for (i = 0; i < n; i++){
		scanf("%d", &L[i]);
		L[i] = 1 << L[i];
	}
	Do(0, L, 1, 0);
	printf("%lld\n", Res);
	return 0;
}

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1236 KB Output is correct
2 Correct 4 ms 1236 KB Output is correct
3 Incorrect 0 ms 1236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1236 KB Output is correct
2 Correct 4 ms 1236 KB Output is correct
3 Incorrect 0 ms 1236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1236 KB Output is correct
2 Correct 48 ms 1236 KB Output is correct
3 Correct 52 ms 1236 KB Output is correct
4 Correct 44 ms 1236 KB Output is correct
5 Correct 56 ms 1236 KB Output is correct
6 Correct 40 ms 1236 KB Output is correct
7 Correct 236 ms 1776 KB Output is correct
8 Correct 164 ms 1592 KB Output is correct
9 Correct 332 ms 2148 KB Output is correct
10 Correct 376 ms 2148 KB Output is correct

Subtask #4
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1236 KB Output is correct
2 Correct 0 ms 1236 KB Output is correct
3 Incorrect 0 ms 1236 KB Output isn't correct
4 Halted 0 ms 0 KB -