Szczegółowe omówienie zadania Korale:

Link do powyższego omówienia zadania Korale: https://youtu.be/RScESwzLWIE?t=1065
Link do treści zadania Korale: https://szkopul.edu.pl/problemset/problem/6×4-Pmy-UoyrQpi19NsAz6Rn/site

Zadanie Korale wykorzystuje hashe: https://youtu.be/RScESwzLWIE?t=348
Do czego potrzebne są hashe? https://youtu.be/dfpERcmogNM?t=1369

Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/

Zajęcia Olimpiada Informatyczna POZIOM II: https://oki.org.pl/olimpiada-informatyczna-poziom-ii/
Wszystkie zajęcia: https://oki.org.pl/harmonogram-zajec/
Informacje o zajęciach: https://oki.org.pl/newsletter.php

–
Kod C++ programu "Korale", który jest omówiony w powyższym filmie i który otrzymuje 100%

–

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 7;
const int P = 314159;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
int arr[MAXN];
int H[MAXN][2];
int H_rev[MAXN][2];
int pow_P[MAXN][2];
// zwraca hash słowa arr[l...r]
pair<int, int> get_hash(int l, int r, int n)
{
pair<int, int> res = { (H[r][0] - H[l-1][0] + MOD1) % MOD1,
(H[r][1] - H[l-1][1] + MOD2) % MOD2 };
return { ((ll)res.first * pow_P[n-l+1][0]) % MOD1,
((ll)res.second * pow_P[n-l+1][1]) % MOD2 };
}
// zwraca hash odwróconego słowa arr[l...r]
pair<int, int> get_hash_rev(int l, int r, int n)
{
pair<int, int> res = { (H_rev[l][0] - H_rev[r+1][0] + MOD1) % MOD1,
(H_rev[l][1] - H_rev[r+1][1] + MOD2) % MOD2 };
return { ((ll)res.first * pow_P[r][0]) % MOD1,
((ll)res.second * pow_P[r][1]) % MOD2 };
}
// zwraca liczbę różnych ciągów długości k
int count_distinct(int k, int n)
{
set<pair<int, int>> prv_h;
int res = 0;
for (int i = 1; (i+k-1) <= n; i += k) {
pair<int, int> H_res = get_hash(i, i+k-1, n);
pair<int, int> H_rev_res = get_hash_rev(i, i+k-1, n);
// jeżeli nie było słowa ani odwróconego słowa
if (prv_h.find(H_res) == prv_h.end() && prv_h.find(H_rev_res) == prv_h.end())
++res;
prv_h.insert(H_res);
}
return res;
}
void hash_init(int n)
{
pow_P[0][0] = pow_P[0][1] = 1;
for (int i = 1; i <= n; ++i) {
pow_P[i][0] = ((ll)pow_P[i-1][0] * P) % MOD1;
pow_P[i][1] = ((ll)pow_P[i-1][1] * P) % MOD2;
}
// liczy hashe
for (int i = 1; i <= n; ++i) {
H[i][0] = ((ll)H[i-1][0] + (ll)arr[i] * pow_P[i-1][0]) % MOD1;
H[i][1] = ((ll)H[i-1][1] + (ll)arr[i] * pow_P[i-1][1]) % MOD2;
}
// liczy odwrócone hashe
for (int i = n; i >= 1; --i) {
        H_rev[i][0] = ((ll)H_rev[i+1][0] + (ll)arr[i] * pow_P[n-i][0]) % MOD1;
H_rev[i][1] = ((ll)H_rev[i+1][1] + (ll)arr[i] * pow_P[n-i][1]) % MOD2;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> arr[i];
hash_init(n);
int ans = 0;
vector<int> ans_k;
for (int k = 1; k <= n; ++k) {
int c = count_distinct(k, n);
if (c > ans) {
ans = c;
ans_k.clear();
}
if (c == ans)
ans_k.push_back(k);
}
cout << ans << ' ' << ans_k.size() << '\n';
for (int i = 0; i < ans_k.size(); ++i)
cout << ans_k[i] << ' ';
cout << '\n';
return 0;
}