| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 208666 | E869120 | Sequence (BOI14_sequence) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <ctime>
using namespace std;
#pragma warning (disable: 4996)
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, ret = 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() {
srand((unsigned)time(NULL));
scanf("%d", &N); init();
for (int i = 0; i < N; i++) scanf("%d", &A[i]);
// ステップ 1. 1000 以下を全探索
for (int i = 1; i <= 100; 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;
}