oj.uz

Submission #54997

# Submission time Handle Problem Language Result Execution time Memory
54997 2018-07-05T18:38:44 Z cki86201 Sequence (BOI14_sequence) C++11
100 / 100
 836 ms 8028 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>
#include <complex.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

namespace fft {
	const int A = 7, B = 26, P = A << B | 1, R = 3;
	const int SZ = 18, N = 1 << SZ;
 
	int Pow(int x, int y) {
		int r = 1;
		while (y) {
			if (y & 1) r = (long long)r * x % P;
			x = (long long)x * x % P;
			y >>= 1;
		}
		return r;
	}
 
	void FFT(int *a, bool f) {
		int i, j, k, x, y, z;
		j = 0;
		for (i = 1; i < N; i++) {
			for (k = N >> 1; j >= k; k >>= 1) j -= k;
			j += k;
			if (i < j) {
				k = a[i];
				a[i] = a[j];
				a[j] = k;
			}
		}
		for (i = 1; i < N; i <<= 1) {
			x = Pow(f ? Pow(R, P - 2) : R, P / i >> 1);
			for (j = 0; j < N; j += i << 1) {
				y = 1;
				for (k = 0; k < i; k++) {
					z = (long long)a[i | j | k] * y % P;
					a[i | j | k] = a[j | k] - z;
					if (a[i | j | k] < 0) a[i | j | k] += P;
					a[j | k] += z;
					if (a[j | k] >= P) a[j | k] -= P;
					y = (long long)y * x % P;
				}
			}
		}
		if (f) {
			j = Pow(N, P - 2);
			for (i = 0; i < N; i++) a[i] = (long long)a[i] * j % P;
		}
	}
	void multiply(int *a, int *b) {
		FFT(a, false);
		FFT(b, false);
		rep(i, N) a[i] = (ll) a[i] * b[i] % P;
		FFT(a, true);
	}
}

int N, A[100010];
int B[100010], BF[1<<18], AF[1<<18];
int trans(int x, int md = 0) {
	int res = 0;
	if(md == 0 && x <= 9999) res |= 1;
	while(x) res |= 1<<(x%10), x /= 10;
	return 1023 - res;
}

int data_x[100010], data_y[100010];
ll get_min(int x) {
	if(x == 0) return 0;
	if(x == 1) return 10;
	ll ans = 0;
	for(int i=1;i<10;i++) if(1<<i&x) {
		ans = 10 * ans + i;
		if(ans < 10 && (x&1)) ans = 10 * ans;
	}
	return ans;
}

ll get_12(int x0, int x1, int md = 0) {
	ll ans = 1e18;
	for(int t=0;t<9;t++) {
		int nx0 = x0 & (1023^(1<<t));
		int nx1 = x1 & (1023^(1<<(t+1)));
		int nx = (nx0 | nx1);
		ll val = get_min(nx);
		if(t == 0 && val == 0) val = 1;
		ans = min(ans, val * 10 + t);
	}
	if((512|x0) == (512) && (3|x1) == 3) ans = min(ans, 9LL);
	if(md == 0) {
		x0 = x0 & (1023^(1<<9));
		x1 = x1 & (1023^(1<<0));
		ans = min(ans, get_12(x0, x1, 1) * 10 + 9);
	}
	return ans;
}

int D[200020];

void solve(){
	scanf("%d", &N);
	rep(i, N) scanf("%d", A+i);
	rep(i, 100000) B[i] = trans(i);
	for(int k=0;k<10;k++) {
		memset(AF, 0, sizeof AF);
		memset(BF, 0, sizeof BF);
		rep(i, N) AF[i] = (A[i] == k % 10);
		rep(i, 100000) BF[i] = !!(B[99999-i] & 1<<k);
		fft::multiply(AF, BF);
		for(int i=0;i<100000;i++) {
			if(AF[i]) data_x[99999-i] |= 1<<k;
			if(AF[i+100000]) data_y[99999-i] |= 1<<k;
		}
	}
	ll ans = 1e18;
	for(int i=0;i<100000;i++) {
		ans = min(ans, get_12(data_x[i], data_y[i]) * 100000 + i);
	}
	for(int i=1;i<=200000;i++) D[i] = trans(i, 1);
	for(int s=1;s<=100000;s++) {
		int ok = 1;
		rep(u, 80) {
			int t = rand() % N;
			if(D[s+t] & 1<<A[t]) { ok = 0; break; }
		}
		if(ok) rep(i, N) if(D[s+i] & 1<<A[i]) { ok = 0; break; }
		if(ok) ans = min(ans, (ll)s);
	}
	printf("%lld\n", ans);
}

int main(){
	int Tc = 1; // scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}

Compilation message

sequence.cpp: In function 'void solve()':
sequence.cpp:130:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
sequence.cpp:131:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i, N) scanf("%d", A+i);
            ~~~~~^~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 836 ms 4048 KB Output is correct
2 Correct 688 ms 4072 KB Output is correct
3 Correct 712 ms 4252 KB Output is correct
4 Correct 761 ms 4252 KB Output is correct
5 Correct 684 ms 4252 KB Output is correct
6 Correct 665 ms 4252 KB Output is correct
7 Correct 668 ms 4252 KB Output is correct
8 Correct 759 ms 4412 KB Output is correct
9 Correct 713 ms 4412 KB Output is correct
10 Correct 720 ms 4412 KB Output is correct
11 Correct 643 ms 4412 KB Output is correct
12 Correct 825 ms 4460 KB Output is correct
13 Correct 661 ms 4460 KB Output is correct
14 Correct 636 ms 4460 KB Output is correct
15 Correct 656 ms 4460 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 4460 KB Output is correct
2 Correct 648 ms 4460 KB Output is correct
3 Correct 656 ms 4460 KB Output is correct
4 Correct 831 ms 4460 KB Output is correct
5 Correct 781 ms 4460 KB Output is correct
6 Correct 736 ms 4460 KB Output is correct
7 Correct 696 ms 4460 KB Output is correct
8 Correct 699 ms 4460 KB Output is correct
9 Correct 652 ms 4460 KB Output is correct
10 Correct 714 ms 4460 KB Output is correct
11 Correct 654 ms 4460 KB Output is correct
12 Correct 731 ms 4460 KB Output is correct
13 Correct 742 ms 4460 KB Output is correct
14 Correct 702 ms 4460 KB Output is correct
15 Correct 715 ms 4460 KB Output is correct
16 Correct 763 ms 4460 KB Output is correct
17 Correct 780 ms 4460 KB Output is correct
18 Correct 739 ms 4500 KB Output is correct
19 Correct 702 ms 4560 KB Output is correct
20 Correct 798 ms 4560 KB Output is correct
21 Correct 712 ms 4560 KB Output is correct
22 Correct 648 ms 4560 KB Output is correct
23 Correct 646 ms 4560 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 4560 KB Output is correct
2 Correct 671 ms 4560 KB Output is correct
3 Correct 756 ms 4560 KB Output is correct
4 Correct 748 ms 4560 KB Output is correct
5 Correct 741 ms 4580 KB Output is correct
6 Correct 818 ms 4580 KB Output is correct
7 Correct 695 ms 5276 KB Output is correct
8 Correct 765 ms 5276 KB Output is correct
9 Correct 680 ms 5844 KB Output is correct
10 Correct 646 ms 5912 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 5912 KB Output is correct
2 Correct 680 ms 5912 KB Output is correct
3 Correct 666 ms 5912 KB Output is correct
4 Correct 660 ms 5912 KB Output is correct
5 Correct 668 ms 5912 KB Output is correct
6 Correct 743 ms 5912 KB Output is correct
7 Correct 658 ms 5912 KB Output is correct
8 Correct 651 ms 5912 KB Output is correct
9 Correct 649 ms 5912 KB Output is correct
10 Correct 721 ms 5912 KB Output is correct
11 Correct 788 ms 6032 KB Output is correct
12 Correct 667 ms 6356 KB Output is correct
13 Correct 648 ms 6356 KB Output is correct
14 Correct 683 ms 6356 KB Output is correct
15 Correct 641 ms 6356 KB Output is correct
16 Correct 636 ms 6356 KB Output is correct
17 Correct 643 ms 6356 KB Output is correct
18 Correct 649 ms 6356 KB Output is correct
19 Correct 682 ms 6356 KB Output is correct
20 Correct 670 ms 6356 KB Output is correct
21 Correct 651 ms 6356 KB Output is correct
22 Correct 713 ms 6356 KB Output is correct
23 Correct 717 ms 6356 KB Output is correct
24 Correct 733 ms 6356 KB Output is correct
25 Correct 749 ms 6356 KB Output is correct
26 Correct 674 ms 6356 KB Output is correct
27 Correct 651 ms 6356 KB Output is correct
28 Correct 685 ms 6356 KB Output is correct
29 Correct 630 ms 6356 KB Output is correct
30 Correct 640 ms 6356 KB Output is correct
31 Correct 665 ms 6356 KB Output is correct
32 Correct 661 ms 6356 KB Output is correct
33 Correct 819 ms 6356 KB Output is correct
34 Correct 689 ms 6948 KB Output is correct
35 Correct 773 ms 7104 KB Output is correct
36 Correct 695 ms 7104 KB Output is correct
37 Correct 687 ms 7488 KB Output is correct
38 Correct 650 ms 7488 KB Output is correct
39 Correct 651 ms 7744 KB Output is correct
40 Correct 671 ms 8028 KB Output is correct