oj.uz

Submission #11099

# Submission time Handle Problem Language Result Execution time Memory
11099 2014-11-13T14:07:03 Z ainta Sequence (BOI14_sequence) C++
0 / 100
 1000 ms 31812 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;
#define SZ 131072
#define INF 9999
long long Res = 99999999999999999LL;
int n;
struct Tree{
	int Min, K, S;
};
struct ST{
	Tree IT[SZ * 2];
	void init(){
		int i;
		for (i = SZ*2-1; i >= 1; i--){
			IT[i].Min = INF;
			if (i >= SZ)IT[i].S = 1;
			else IT[i].S = IT[i * 2].S + IT[i * 2 + 1].S;
		}
	}
	void UDT(int node){
		int c1 = node * 2, c2 = node * 2 + 1;
		if (IT[c1].Min < IT[c2].Min)IT[node].Min = IT[c1].Min, IT[node].S = IT[c1].S;
		else if (IT[c1].Min > IT[c2].Min)IT[node].Min = IT[c2].Min, IT[node].S = IT[c2].S;
		else IT[node].Min = IT[c1].Min, IT[node].S = IT[c1].S + IT[c2].S;
	}
	void First_Ins(int t){
		t += SZ;
		IT[t].Min = 0, IT[t].S = 1;
		while (t>1){
			t >>= 1;
			UDT(t);
		}
	}
	void Add(int node, int x){
		IT[node].Min += x, IT[node].K += x;
	}
	void Ins(int node, int b, int e, int s, int l, int x){
		if (b == s && e == l){
			Add(node, x);
			return;
		}
		Add(node * 2, IT[node].K);
		Add(node * 2 + 1, IT[node].K);
		IT[node].K = 0;
		int m = (b + e) >> 1;
		if (s <= m)Ins(node * 2, b, m, s, min(m, l), x);
		if (l > m)Ins(node * 2 + 1, m + 1, e, max(m + 1, s), l, x);
		UDT(node);
	}
}SegTree[10];
void DFS(int Num, int p, int ck){
	int i, j, t, r = 0;
	if (Num == 7){
		t = 0;
	}
	if (ck){
		long long S = Num, P = p;
		int tt = -1;
		if (!SegTree[0].IT[1].Min){
			for (i = 1; i < 10; i++){
				if (!SegTree[i].IT[1].Min)tt = i;
			}
			if (tt == -1){
				S += P * 10;
			}
			else{
				for (i = 9; i >= 0; i--){
					if (!SegTree[i].IT[1].Min){
						if (tt == i)P *= 10;
						S += P*i;
						P *= 10;
					}
				}
			}
		}
		else{
			for (i = 9; i >= 0; i--){
				if (!SegTree[i].IT[1].Min){
					S += P*i;
					P = P * 10;
				}
			}
		}
		Res = min(Res, S);
		return;
	}
	for (i = 0; i < 10; i++){
		if (!SegTree[i].IT[1].Min)r++;
	}
	if (r == 0){
		if (Num / (p / 10) == 0){
			Res = min(Res, (long long)Num + p);
		}
		else Res = min(Res, (long long)Num);
		return;
	}
	if (p == 1000000){
		if (Num > 1000000-n){
			for (i = 0; i < 9; i++){
				SegTree[i].Ins(1, 1, SZ, 1, 1000000 - Num, 1);
				SegTree[(i + 1) % 10].Ins(1, 1, SZ, 1000001 - Num, n, 1);
				DFS(Num + p*i, p*10, 1);
				SegTree[i].Ins(1, 1, SZ, 1, 1000000 - Num, -1);
				SegTree[(i + 1) % 10].Ins(1, 1, SZ, 1000001 - Num, n, -1);
			}
			return;
		}
		else{
			DFS(Num, p, 1);
		}
		return;
	}
	for (i = 0; i < 10; i++){
		t = i;
		SegTree[t].Ins(1, 1, SZ, 1, min(p - Num, n), 1);
		for (j = p - Num + 1; j <= n; j += p){
			t++;
			if (t == 10)t = 0;
			SegTree[t].Ins(1, 1, SZ, j, min(j + p - 1, n), 1);
		}
		DFS(Num + p*i, p * 10, 0);
		t = i;
		SegTree[t].Ins(1, 1, SZ, 1, min(p - Num, n), -1);
		for (j = p - Num + 1; j <= n; j += p){
			t++;
			if (t == 10)t = 0;
			SegTree[t].Ins(1, 1, SZ, j, min(j + p - 1, n), -1);
		}
	}
}
int main()
{
	scanf("%d", &n);
	int i, a, j, t;
	for (i = 0; i < 10; i++){
		SegTree[i].init();
	}
	for (i = 1; i <= n; i++){
		scanf("%d", &a);
		SegTree[a].First_Ins(i - 1);
	}
	DFS(0, 1, 0);
	printf("%lld\n", Res);
}

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 904 ms 31812 KB Output is correct
2 Execution timed out 1000 ms 31812 KB Program timed out
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 920 ms 31812 KB Output is correct
2 Execution timed out 1000 ms 31812 KB Program timed out
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 31812 KB Output is correct
2 Execution timed out 1000 ms 31812 KB Program timed out
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 956 ms 31812 KB Output is correct
2 Execution timed out 1000 ms 31812 KB Program timed out
3 Halted 0 ms 0 KB -