oj.uz

Submission #208664

# Submission time Handle Problem Language Result Execution time Memory
208664 2020-03-12T01:37:23 Z E869120 Sequence (BOI14_sequence) C++14
67 / 100
 1000 ms 1184 KB 
#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); }
		if (J[i].size() >= 1) {
			for (int j = 0; j < 200; j++) swap(J[i][rand() % J[i].size()], J[i][rand() % J[i].size()]);
		}
	}

	// ケース 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;
}

Compilation message

sequence.cpp:7:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
sequence.cpp: In function 'long long int solve(int)':
sequence.cpp:65:16: warning: unused variable 'ret' [-Wunused-variable]
  int maxt = 0, ret = 0;
                ^~~
sequence.cpp: In function 'int main()':
sequence.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N); init();
  ~~~~~^~~~~~~~~~
sequence.cpp:117:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; i++) scanf("%d", &A[i]);
                              ~~~~~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 442 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 437 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 230 ms 504 KB Output is correct
8 Correct 219 ms 504 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 448 ms 504 KB Output is correct
11 Correct 5 ms 508 KB Output is correct
12 Correct 415 ms 556 KB Output is correct
13 Correct 441 ms 504 KB Output is correct
14 Correct 464 ms 588 KB Output is correct
15 Correct 466 ms 632 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 454 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 416 ms 504 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 7 ms 504 KB Output is correct
7 Correct 231 ms 632 KB Output is correct
8 Correct 208 ms 504 KB Output is correct
9 Correct 224 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 375 ms 600 KB Output is correct
12 Correct 468 ms 588 KB Output is correct
13 Correct 5 ms 504 KB Output is correct
14 Correct 431 ms 504 KB Output is correct
15 Correct 457 ms 600 KB Output is correct
16 Correct 479 ms 608 KB Output is correct
17 Correct 476 ms 628 KB Output is correct
18 Correct 421 ms 504 KB Output is correct
19 Correct 458 ms 504 KB Output is correct
20 Correct 493 ms 608 KB Output is correct
21 Correct 449 ms 608 KB Output is correct
22 Correct 497 ms 596 KB Output is correct
23 Correct 465 ms 608 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 508 KB Output is correct
2 Correct 296 ms 632 KB Output is correct
3 Correct 288 ms 656 KB Output is correct
4 Correct 345 ms 632 KB Output is correct
5 Correct 333 ms 632 KB Output is correct
6 Correct 274 ms 632 KB Output is correct
7 Correct 701 ms 996 KB Output is correct
8 Correct 546 ms 868 KB Output is correct
9 Correct 936 ms 1176 KB Output is correct
10 Correct 919 ms 1184 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 457 ms 604 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 446 ms 608 KB Output is correct
5 Execution timed out 1068 ms 860 KB Time limit exceeded
6 Halted 0 ms 0 KB -