#include <iostream>
#include <vector>
void print_vec_pair(std::vector<std::pair<int, int>>& v) {
for (const auto& a : v) {
std::cout << "(" << a.first << ", " << a.second << ") ";
}
std::cout << std::endl;
}
bool compare_pairs(std::pair<int, int>& a, std::pair<int, int>& b) {
if (a.second == b.second)
return true;
else
return false;
}
size_t find_seq_len (std::vector<std::pair<int, int>> & data, size_t start, size_t end) {
size_t len = 0;
if (start == end) {
return 1;
}
do {
len++;
} while ( compare_pairs(data[start], data[start+len]) );
return len;
}
bool is_present(std::vector<std::pair<int, int>>& data, std::pair<int, int>& p) {
if (data.back().first == p.first) {
return true;
}
else {
return false;
}
}
std::vector<std::pair<int, int>> decimation(std::vector<std::pair<int, int>>& data, int N) {
if (N <= 2 || data.size() == 0) {
return std::vector<std::pair<int, int>>();
}
std::vector<std::pair<int, int>> res;
for (size_t i = 0; i < data.size(); ) {
size_t len = find_seq_len(data, i, data.size() - 1);
res.push_back(data[i]);
for (size_t j = 1; j < len; j++) {
if (j % N == 0) {
res.push_back(data[i + j - 1]);
}
}
if (is_present(res, data[i + len - 1]) == false) {
res.push_back(data[i + len - 1]);
}
i+=len;
}
return res;
}
int main()
{
std::vector<std::pair<int, int>> data;
data.push_back({ 1, 10 });
data.push_back({ 2, 11 });
data.push_back({ 3, 11 });
data.push_back({ 4, 11 });
data.push_back({ 5, 11 });
data.push_back({ 6, 10 });
data.push_back({ 7, 11 });
data.push_back({ 8, 11 });
data.push_back({ 9, 11 });
data.push_back({ 10, 11 });
data.push_back({ 11, 11 });
data.push_back({ 12, 11 });
data.push_back({ 13, 11 });
data.push_back({ 14, 10 });
auto result3 = decimation(data, 3);
auto result4 = decimation(data, 4);
print_vec_pair(data);
std::cout << std::endl;
print_vec_pair(result3);
std::cout << std::endl;
print_vec_pair(result4);
std::cout << std::endl;
}
CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHZlY3Rvcj4KCnZvaWQgcHJpbnRfdmVjX3BhaXIoc3RkOjp2ZWN0b3I8c3RkOjpwYWlyPGludCwgaW50Pj4mIHYpIHsKCglmb3IgKGNvbnN0IGF1dG8mIGEgOiB2KSB7CgkJc3RkOjpjb3V0IDw8ICIoIiA8PCBhLmZpcnN0IDw8ICIsICIgPDwgYS5zZWNvbmQgPDwgIikgIjsKCX0KCXN0ZDo6Y291dCA8PCBzdGQ6OmVuZGw7Cn0KCmJvb2wgY29tcGFyZV9wYWlycyhzdGQ6OnBhaXI8aW50LCBpbnQ+JiBhLCBzdGQ6OnBhaXI8aW50LCBpbnQ+JiBiKSB7CgoJaWYgKGEuc2Vjb25kID09IGIuc2Vjb25kKQoJCXJldHVybiB0cnVlOwoJZWxzZQoJCXJldHVybiBmYWxzZTsKfQoKCnNpemVfdCBmaW5kX3NlcV9sZW4gKHN0ZDo6dmVjdG9yPHN0ZDo6cGFpcjxpbnQsIGludD4+ICYgZGF0YSwgc2l6ZV90IHN0YXJ0LCBzaXplX3QgZW5kKSB7CgoJc2l6ZV90IGxlbiA9IDA7CglpZiAoc3RhcnQgPT0gZW5kKSB7CgkJcmV0dXJuIDE7Cgl9CglkbyB7CgkJbGVuKys7Cgl9IHdoaWxlICggIGNvbXBhcmVfcGFpcnMoZGF0YVtzdGFydF0sIGRhdGFbc3RhcnQrbGVuXSkgICk7CgoJcmV0dXJuIGxlbjsKfQoKYm9vbCBpc19wcmVzZW50KHN0ZDo6dmVjdG9yPHN0ZDo6cGFpcjxpbnQsIGludD4+JiBkYXRhLCBzdGQ6OnBhaXI8aW50LCBpbnQ+JiBwKSB7CglpZiAoZGF0YS5iYWNrKCkuZmlyc3QgPT0gcC5maXJzdCkgewoJCXJldHVybiB0cnVlOwoJfQoJZWxzZSB7CgkJcmV0dXJuIGZhbHNlOwoJfQp9CgpzdGQ6OnZlY3RvcjxzdGQ6OnBhaXI8aW50LCBpbnQ+PiBkZWNpbWF0aW9uKHN0ZDo6dmVjdG9yPHN0ZDo6cGFpcjxpbnQsIGludD4+JiBkYXRhLCBpbnQgTikgewoKCWlmIChOIDw9IDIgfHwgZGF0YS5zaXplKCkgPT0gMCkgewoJCXJldHVybiBzdGQ6OnZlY3RvcjxzdGQ6OnBhaXI8aW50LCBpbnQ+PigpOwoJfQoKCXN0ZDo6dmVjdG9yPHN0ZDo6cGFpcjxpbnQsIGludD4+IHJlczsKCglmb3IgKHNpemVfdCBpID0gMDsgaSA8IGRhdGEuc2l6ZSgpOyApIHsKCQoJCXNpemVfdCBsZW4gPSBmaW5kX3NlcV9sZW4oZGF0YSwgaSwgZGF0YS5zaXplKCkgLSAxKTsKCgkJcmVzLnB1c2hfYmFjayhkYXRhW2ldKTsKCQlmb3IgKHNpemVfdCBqID0gMTsgaiA8IGxlbjsgaisrKSB7CgkJCWlmIChqICUgTiA9PSAwKSB7CgkJCQlyZXMucHVzaF9iYWNrKGRhdGFbaSArIGogLSAxXSk7CgkJCX0KCQl9CgoJCWlmIChpc19wcmVzZW50KHJlcywgZGF0YVtpICsgbGVuIC0gMV0pID09IGZhbHNlKSB7CgkJCXJlcy5wdXNoX2JhY2soZGF0YVtpICsgbGVuIC0gMV0pOwoJCX0KCgkJaSs9bGVuOwoJfQoKCXJldHVybiByZXM7Cn0KCgppbnQgbWFpbigpCnsKCXN0ZDo6dmVjdG9yPHN0ZDo6cGFpcjxpbnQsIGludD4+IGRhdGE7CglkYXRhLnB1c2hfYmFjayh7IDEsIDEwIH0pOwoJZGF0YS5wdXNoX2JhY2soeyAyLCAxMSB9KTsKCWRhdGEucHVzaF9iYWNrKHsgMywgMTEgfSk7CglkYXRhLnB1c2hfYmFjayh7IDQsIDExIH0pOwoJZGF0YS5wdXNoX2JhY2soeyA1LCAxMSB9KTsKCWRhdGEucHVzaF9iYWNrKHsgNiwgMTAgfSk7CglkYXRhLnB1c2hfYmFjayh7IDcsIDExIH0pOwoJZGF0YS5wdXNoX2JhY2soeyA4LCAxMSB9KTsKCWRhdGEucHVzaF9iYWNrKHsgOSwgMTEgfSk7CglkYXRhLnB1c2hfYmFjayh7IDEwLCAxMSB9KTsKCWRhdGEucHVzaF9iYWNrKHsgMTEsIDExIH0pOwoJZGF0YS5wdXNoX2JhY2soeyAxMiwgMTEgfSk7CglkYXRhLnB1c2hfYmFjayh7IDEzLCAxMSB9KTsKCWRhdGEucHVzaF9iYWNrKHsgMTQsIDEwIH0pOwoKCWF1dG8gcmVzdWx0MyA9IGRlY2ltYXRpb24oZGF0YSwgMyk7CglhdXRvIHJlc3VsdDQgPSBkZWNpbWF0aW9uKGRhdGEsIDQpOwoJCglwcmludF92ZWNfcGFpcihkYXRhKTsKCXN0ZDo6Y291dCA8PCBzdGQ6OmVuZGw7CgkKCXByaW50X3ZlY19wYWlyKHJlc3VsdDMpOwoJc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKCQoJcHJpbnRfdmVjX3BhaXIocmVzdWx0NCk7CglzdGQ6OmNvdXQgPDwgc3RkOjplbmRsOwoKfQ==
(1, 10) (2, 11) (3, 11) (4, 11) (5, 11) (6, 10) (7, 11) (8, 11) (9, 11) (10, 11) (11, 11) (12, 11) (13, 11) (14, 10)
(1, 10) (2, 11) (4, 11) (5, 11) (6, 10) (7, 11) (9, 11) (12, 11) (13, 11) (14, 10)
(1, 10) (2, 11) (5, 11) (6, 10) (7, 11) (10, 11) (13, 11) (14, 10)