Pagini recente » Cod sursa (job #182833) | Cod sursa (job #1746124) | Cod sursa (job #1873808) | Cod sursa (job #1784090) | Cod sursa (job #2265820)
#include <cstdint>
#include <fstream>
#include <vector>
using namespace std;
size_t SamePrefixLen(const vector<int64_t> &vec, size_t left, size_t right)
{
size_t len = 0;
while (right + len < vec.size() && vec[left + len] == vec[right + len]) {
len += 1;
}
return len;
}
vector<size_t> FindZVec(const vector<int64_t> &vec)
{
vector<size_t> zvec(vec.size(), 0);
size_t left = 0, right = 0;
for (size_t i = 1; i < vec.size(); i += 1) {
if (i > right) {
zvec[i] = SamePrefixLen(vec, 0, i);
left = i;
right = i + zvec[i] - 1;
continue;
}
auto other = i - left;
auto len_to_right = right - i + 1;
if (zvec[other] < len_to_right) {
zvec[i] = zvec[other];
} else {
auto extra = SamePrefixLen(vec, len_to_right, right + 1);
zvec[i] = len_to_right + extra;
left = i;
right = i + zvec[i] - 1;
}
}
return zvec;
}
bool HasPeriod(const vector<size_t> &zvec,
const vector<int64_t> &vec,
size_t period)
{
if (period <= 0) {
return false;
}
size_t len = period;
while (len < zvec.size() && zvec[len] >= period) {
len += period;
}
auto to_check = zvec.size() - len;
if (to_check >= period) {
return false;
}
for (size_t i = 0; i < to_check; i += 1) {
if (vec[i] != vec[len + i]) {
return false;
}
}
return true;
}
size_t FindPeriod(const vector<int64_t> &vec)
{
auto zvec = FindZVec(vec);
auto period = vec.size();
for (size_t i = 1; i < vec.size(); i += 1) {
if (HasPeriod(zvec, vec, i)) {
period = i;
break;
}
}
return period;
}
int main()
{
ifstream fin("reguli.in");
ofstream fout("reguli.out");
int n;
fin >> n;
vector<int64_t> vec(n - 1);
fin >> vec[0];
for (auto i = 1; i < n; i += 1) {
int64_t num;
fin >> num;
vec[i - 1] = num - vec[i - 1];
if (i + 1 < n) {
vec[i] = num;
}
}
auto period = FindPeriod(vec);
fout << period << "\n";
for (size_t i = 0; i < period; i += 1) {
fout << vec[i] << "\n";
}
return 0;
}