#include <iostream>
#include <vector>
#include <cstdint>
#include <functional>
void compress(const std::vector<uint8_t>& source, std::vector<uint8_t>& result) {
result.clear();
if (source.empty()) {
return;
}
ptrdiff_t windowStart = 0;
bool isContinuous = false;
using ResolveFunc = std::function<void(int)>;
ResolveFunc resolveDiscontinuous = [&](int endIndex) -> void { // 处理不连续部分
// 使用模式0，填入[length, ...source[windowStart .. idx]]
result.push_back(endIndex - windowStart);
result.insert(result.end(), source.begin() + windowStart, source.begin() + endIndex);
windowStart = endIndex;
};
ResolveFunc resolveContinuous = [&](int endIndex) -> void { // 处理连续部分
// 使用模式1，填入[0x80 | length, source[windowStart]]
result.push_back(0x80 | (endIndex - windowStart));
result.push_back(source[windowStart]);
windowStart = endIndex;
};
for (ptrdiff_t idx = 1; idx < source.size(); idx++) {
if (source[idx] == source[idx - 1]) {
if (!isContinuous) {
// 不连续段结束
isContinuous = true;
if (idx - windowStart > 1) {
resolveDiscontinuous(idx - 1);
}
continue;
}
} else {
if (isContinuous) {
// 连续段结束，使用模式1
isContinuous = false;
resolveContinuous(idx);
continue;
}
}
if (idx - windowStart == 0x7F) {
// 超过最大长度了，需要截断
(isContinuous ? resolveContinuous : resolveDiscontinuous)(idx);
}
}
// 处理剩下的
(isContinuous ? resolveContinuous : resolveDiscontinuous)(source.size());
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(0);
std::cin.tie(0);
#endif
size_t length;
std::cin >> length;
auto source = std::vector<uint8_t>(length);
auto compressed = std::vector<uint8_t>();
for (auto& v : source) {
int num;
std::cin >> num;
v = static_cast<uint8_t>(num);
}
compress(source, compressed);
std::cout << compressed.size() << '\n';
for (auto& v : compressed) {
std::cout << static_cast<int>(v) << ' ';
}
}
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdint>
#include <functional>
bool decompress(const std::vector<uint8_t>& source, std::vector<uint8_t>& output, size_t maxLength) {
const uint8_t ctrlMask = 0x80;
ptrdiff_t index = 0; // 在64位计算机上，ptrdiff_t就是int64_t，32位则是int32_t
while (index < source.size()) {
uint8_t length = source[index] & (~ctrlMask);
if (source[index++] & ctrlMask) {
if (index >= source.size())
return false;
uint8_t value = source[index++];
output.insert(output.end(), length, value);
} else {
if (index + length - 1 >= source.size())
return false;
auto itStart = source.begin() + index;
output.insert(output.end(), itStart, itStart + length);
index += length;
}
if (output.size() > maxLength) { // 防一手
return false;
}
}
return true;
}
inline bool read(std::istream& in, std::vector<uint8_t>& data) {
size_t length;
if (!(in >> length)) {
return false;
}
data.resize(length);
for (size_t i = 0; i < length; i++) {
int value;
if (!(in >> value)) {
return false;
}
if (value < 0 || value > 255) {
return false; // 确保值在uint8_t范围内
}
data[i] = static_cast<uint8_t>(value);
}
while (in.peek() == '\n' || in.peek() == '\r' || in.peek() == ' ') {
in.ignore();
}
if (in.peek() != EOF) {
return false; // 确保没有多余的字符
}
return true;
}
bool sequenceEqual(const std::vector<uint8_t>& a, const std::vector<uint8_t>& b) {
if (a.size() != b.size()) {
return false;
}
for (size_t i = 0; i < a.size(); i++) {
if (a[i] != b[i]) {
return false;
}
}
return true;
}
int main() {
std::ifstream in("input");
std::ifstream out("output");
std::ifstream user_out("user_output");
std::vector<uint8_t> userCompressionData;
std::vector<uint8_t> userDecompressedData;
std::vector<uint8_t> rawData;
size_t rightCompressionLength;
out >> rightCompressionLength;
if (!read(user_out, userCompressionData)) {
return 1; // 用户输出数据读取失败，直接错
}
if (rightCompressionLength != userCompressionData.size()) {
return 1; // 压缩后的数据长度不一致，并非最优解，直接错
}
read(in, rawData);
auto decompressSuccess = decompress(userCompressionData, userDecompressedData, rawData.size());
if (!decompressSuccess) {
return 1; // 解压失败，直接错
}
return sequenceEqual(userDecompressedData, rawData) ? 0 : 1; // 和原来的数据比较
}
