Untitled
unknown
plain_text
2 years ago
2.0 kB
3
Indexable
#include <functional> #include <algorithm> #include <iostream> #include <memory.h> #include <sstream> #include <assert.h> #include <fstream> #include <iomanip> #include <bitset> #include <string> #include <cstdio> #include <complex> #include <vector> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <set> #include <map> using namespace std; #define int64 long long #define mp make_pair const int inf = 1e9; #ifdef _DEBUG const int N = 100; #else const int N = 300100; #endif int n, a[N], b[N], z1[N], z2[N], z3[N], c[N]; vector <int> res; void build(int *a, int *z, int n) { int l = 1, r = 0; for (int i = 2; i <= 2 * n + 1; i++) { if (i <= r) z[i] = min(z[i - l + 1], r - i + 1); while (i + z[i] <= 2 * n + 1 && a[i + z[i]] == a[z[i] + 1]) z[i]++; if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; } } } int main() { freopen("beginend.in", "r", stdin); freopen("beginend.out", "w", stdout); scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) scanf("%d", &b[i]); for (int i = 1; i <= n; i++) c[i] = b[i]; c[n + 1] = -1; for (int i = 1; i <= n; i++) c[i + n + 1] = a[i]; build(c, z1, n); for (int i = 1; i <= n; i++) c[i] = a[i]; for (int i = 1; i <= n; i++) c[i + n + 1] = b[i]; build(c, z2, n); for (int i = 1; i <= n; i++) c[n - i + 1] = b[i]; for (int i = 1; i <= n; i++) c[i + n + 1] = a[i]; build(c, z3, n); for (int i = 1; i <= n; i++) if ((n - i + 1) % 2 == 0) { if (z1[n + 1 + i] >= n - i + 1 && z2[2 * n - i + 3] >= i - 1) res.push_back(i); } else { if (z1[n + 1 + i] >= n - i + 1 && z3[n + 2] >= i - 1) res.push_back(i); } printf("%d\n", res.size()); for (int i = 0; i < res.size(); i++) printf("%d ", res[i]); return 0; }
Editor is loading...