#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;
while(x) res |= 1<<(x%10), x /= 10;
if(md == 0 && x <= 9999) res |= 1;
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));
}
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);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
711 ms |
4164 KB |
Output is correct |
| 2 |
Correct |
757 ms |
4208 KB |
Output is correct |
| 3 |
Correct |
745 ms |
4300 KB |
Output is correct |
| 4 |
Correct |
725 ms |
4300 KB |
Output is correct |
| 5 |
Correct |
673 ms |
4416 KB |
Output is correct |
| 6 |
Correct |
732 ms |
4568 KB |
Output is correct |
| 7 |
Correct |
688 ms |
4568 KB |
Output is correct |
| 8 |
Correct |
778 ms |
4568 KB |
Output is correct |
| 9 |
Correct |
729 ms |
4568 KB |
Output is correct |
| 10 |
Correct |
716 ms |
4568 KB |
Output is correct |
| 11 |
Correct |
742 ms |
4568 KB |
Output is correct |
| 12 |
Correct |
685 ms |
4568 KB |
Output is correct |
| 13 |
Correct |
670 ms |
4644 KB |
Output is correct |
| 14 |
Correct |
801 ms |
4644 KB |
Output is correct |
| 15 |
Correct |
646 ms |
4644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
698 ms |
4644 KB |
Output is correct |
| 2 |
Correct |
681 ms |
4644 KB |
Output is correct |
| 3 |
Correct |
725 ms |
4680 KB |
Output is correct |
| 4 |
Correct |
673 ms |
4680 KB |
Output is correct |
| 5 |
Correct |
657 ms |
4680 KB |
Output is correct |
| 6 |
Correct |
665 ms |
4736 KB |
Output is correct |
| 7 |
Correct |
644 ms |
4740 KB |
Output is correct |
| 8 |
Correct |
691 ms |
4740 KB |
Output is correct |
| 9 |
Correct |
654 ms |
4740 KB |
Output is correct |
| 10 |
Correct |
671 ms |
4740 KB |
Output is correct |
| 11 |
Incorrect |
665 ms |
4788 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
685 ms |
4788 KB |
Output is correct |
| 2 |
Correct |
633 ms |
4808 KB |
Output is correct |
| 3 |
Incorrect |
655 ms |
4852 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
868 ms |
4852 KB |
Output is correct |
| 2 |
Correct |
634 ms |
4880 KB |
Output is correct |
| 3 |
Correct |
643 ms |
4920 KB |
Output is correct |
| 4 |
Correct |
696 ms |
4920 KB |
Output is correct |
| 5 |
Incorrect |
672 ms |
5220 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
