Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdio.h>
- #include <vector>
- #include <algorithm>
- #include <set>
- #include <string.h>
- #include <math.h>
- #include <queue>
- #define pb push_back
- #define sz size
- #define ll long long
- #define fs first
- #define sc second
- #define mp make_pair
- #define bg begin
- #define ers erase
- #define ins insert
- const int INF = 2147483647;
- const int MOD = 1000000007;
- using namespace std;
- ll base1 = 1000000009, base2 = 1000000007;
- int main(){
- //freopen("input.txt", "r", stdin);
- freopen("cubes.in", "r", stdin);
- freopen("cubes.out", "w", stdout);
- int n, m;
- ll t;
- scanf("%d%d", &n, &m);
- ll p = m + 1;
- vector<ll> a, po1, po2;
- for (int i = 0; i < n; i++){
- scanf("%lld", &t);
- a.pb(t);
- }
- po1.pb(1);
- po2.pb(1);
- for (int i = 1; i <= n; i++){
- po1.pb(po1[i - 1] * p % base1);
- po2.pb(po2[i - 1] * p % base2);
- //cout << po1[i] << " " << po2[i] << "\n";
- }
- vector<pair<ll, ll> > h1, h2;
- h1.pb(mp(a[0], a[0]));
- h2.pb(mp(a[n - 1], a[n - 1]));
- for (int i = 1; i < n; i++){
- h1.pb(mp((a[i] * po1[i] % base1 + h1[i - 1].fs) % base1, (a[i] * po2[i] % base2 + h1[i - 1].sc) % base2));
- h2.pb(mp((a[n - i - 1] * po1[i] % base1 + h2[i - 1].fs) % base1, (a[n - i - 1] * po2[i] % base2 + h2[i - 1].sc) % base2));
- }
- pair<ll, ll> t1, t2;
- vector<int> ans;
- for (int i = 1; i <= n / 2; i++){
- t1.fs = h1[i].fs;
- t1.sc = h1[i].sc;
- //cout << i << " " << n - i << " " << n - i * 2 << "\n";
- t2.fs = h2[n - i].fs;
- if (n - i * 2) t2.fs -= h2[n - i * 2 - 1].fs;
- t2.sc = h2[n - i].sc;
- if (n - i * 2) t2.sc -= h2[n - i * 2 - 1].sc;
- if (t2.fs < 0) t2.fs += base1;
- if (t2.sc < 0) t2.sc += base2;
- //cout << t1.fs * po1[n - 2 * i] << " " << t2.fs << " " << t1.sc * po2[n - 2 * i] << " " << t2.sc << " " << i << "\n";
- if (t1.fs * po1[n - 2 * i] % base1 == t2.fs && t1.sc * po2[n - 2 * i] % base2 == t2.sc)
- ans.pb(n - i);
- }
- reverse(ans.bg(), ans.end());
- ans.pb(n);
- for (int i = 0; i < ans.sz(); i++)
- cout << ans[i] << " ";
- return 0;
- }
Add Comment
Please, Sign In to add comment