oj.uz

Submission #208660

# Submission time Handle Problem Language Result Execution time Memory
208660 2020-03-12T01:34:15 Z E869120 Sequence (BOI14_sequence) C++14
0 / 100
 1000 ms 888 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int N, A[1 << 18];
bool used[10000009][10];
bool used3[1009][10];
bool used4[10009][10];

void init() {
	for (int i = 0; i < 10000; i++) {
		int cx = i;
		while (cx >= 1) {
			used[i][cx % 10] = true;
			cx /= 10;
		}
	}
	for (int i = 0; i < 1000; i++) {
		int cx = i;
		for (int j = 0; j < 3; j++) {
			used3[i][cx % 10] = true;
			cx /= 10;
		}
	}
	for (int i = 0; i < 10000; i++) {
		int cx = i;
		for (int j = 0; j < 4; j++) {
			used4[i][cx % 10] = true;
			cx /= 10;
		}
	}
}

bool check(int pos) {
	for (int i = 0; i < N; i++) {
		if (used[pos][A[i]] == false) return false;
		pos++;
	}
	return true;
}

int cnt[109][10];

string fixes(string V, bool flag) {
	if (V == "") {
		if (flag == true) V = "1";
		else V = "0";
	}
	else if (V[0] == '0') {
		if (V.size() == 1) V = "10";
		else swap(V[0], V[1]);
	}
	return V;
}

long long solve(int dig) {
	for (int i = 0; i < 101; i++) {
		for (int j = 0; j < 10; j++) cnt[i][j] = 0;
	}

	int maxt = 0;
	for (int i = 0; i < N; i++) {
		int V1 = (dig + i) % 1000;
		int V2 = (dig + i) / 1000;
		maxt = max(maxt, V2);
		if (used3[V1][A[i]] == true) continue;
		cnt[maxt][A[i]] = 1;
	}

	vector<int> J[10];
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j <= maxt; j++) { if (cnt[j][i] == 1) J[i].push_back(j); }
	}

	// ケース 1: 下 3 桁が XYZ の場合
	long long m1 = (1LL << 60);
	for (int i = 0; i < 900; i++) {
		int v[10] = { 0,0,0,0,0,0,0,0,0,0 }; bool flag = false;
		for (int k = 0; k < 10; k++) {
			for (int j : J[k]) { if (used3[i + j][k] == false) { v[k] = 1; break; } }
		}
		for (int j : J[0]) { if (used[i + j][0] == false) { flag = true; break; } }
		string S = ""; for (int j = 0; j < 10; j++) { if (v[j] == 1) S += ('0' + j); }
		S = fixes(S, flag);
		long long eval = 1000000LL * stoll(S) + 1000LL * i + dig;
		m1 = min(m1, eval);
	}

	// ケース 2: 下 4 桁が X9YZ の場合
	long long m2 = (1LL << 60);
	for (int i = 0; i < 9000; i++) {
		if ((i % 1000) <= 899) continue;
		int v[10] = { 0,0,0,0,0,0,0,0,0,0 }; bool flag = false;
		for (int k = 0; k < 10; k++) {
			for (int j : J[k]) { if (used4[i + j][k] == false) { v[k] = 1; break; } }
		}
		for (int j : J[0]) { if (used[i + j][0] == false) { flag = true; break; } }
		string S = ""; for (int j = 0; j < 10; j++) { if (v[j] == 1) S += ('0' + j); }
		S = fixes(S, flag);
		long long eval = 10000000LL * stoll(S) + 1000LL * i + dig;
		m2 = min(m2, eval);
	}

	return min(m1, m2);
}

int main() {
	cin >> N; init();
	for (int i = 0; i < N; i++) cin >> A[i];

	// ステップ 1. 1000 以下を全探索
	/*for (int i = 1; i <= 1000; i++) {
		if (check(i) == true) {
			cout << i << endl;
			return 0;
		}
	}*/

	// ステップ 2. そうでない場合
	long long minx = (1LL << 60);
	for (int i = 0; i <= 999; i++) {
		minx = min(minx, solve(i));
	}
	cout << minx << endl;
	return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 632 KB Output is correct
2 Correct 352 ms 504 KB Output is correct
3 Correct 348 ms 588 KB Output is correct
4 Correct 352 ms 504 KB Output is correct
5 Incorrect 220 ms 504 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 504 KB Output is correct
2 Correct 349 ms 504 KB Output is correct
3 Correct 341 ms 584 KB Output is correct
4 Correct 330 ms 504 KB Output is correct
5 Incorrect 231 ms 632 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 192 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 504 KB Output is correct
2 Correct 386 ms 632 KB Output is correct
3 Correct 329 ms 504 KB Output is correct
4 Correct 344 ms 632 KB Output is correct
5 Execution timed out 1062 ms 888 KB Time limit exceeded
6 Halted 0 ms 0 KB -