1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <string>
#include <list>

struct node {
    node *parent = NULL;
    int value = 0;
    int index = 0;
    int depth = 1;
    std::list<node> subs;
};

node *prepare_node(int value, int index, node *parent) {
    node *new_node = new node();
    new_node->parent = parent;
    new_node->index = index;
    new_node->value = value;
    return new_node;
}

void increment_parents_depth(node &tree_node) {
    node *parent_node = tree_node.parent;
    if (parent_node != NULL) {
        parent_node->depth = std::max(tree_node.depth + 1, parent_node->depth);
        increment_parents_depth(*parent_node);
    }
}

void add_new_tree_element(node &tree_node, int value, int index) {

    if (tree_node.subs.empty()) { //first element
        node *to_add = prepare_node(value, index, &tree_node);
        tree_node.depth = 2;
        increment_parents_depth(tree_node);
        tree_node.subs.push_back(*to_add);
    } else { //add next elem
        bool at_least_once_added = false;
        for (node &sub: tree_node.subs) {
            if (value > sub.value) { //add to existing sub-nodes in case greater
                add_new_tree_element(sub, value, index);
                at_least_once_added = true;
            }
        };

        if (!at_least_once_added) { //add to the current node in case not greater than existing
            node *to_add = prepare_node(value, index, &tree_node);
            tree_node.subs.push_back(*to_add);
        }
    }
}

void print_tree(node &root, std::string marker) {
    std::string node_value = std::to_string(root.value);
    if (root.value == 0) node_value = "ROOT";

    std::cout << marker << "(" << node_value
    << ", depth=" << root.depth
    << ")" << "\n";
    std::string new_marker = marker + "-";
    for (node &sub: root.subs) {
        print_tree(sub, new_marker);
    }
}

int main() {
    ///----------- INPUT
    std::string line1;
            //"6 3";
            //"4 2";
    std::getline(std::cin, line1);
    int separatorIndex = line1.find(' ');
    std::string nString = line1.substr(0, separatorIndex);
    std::string kString = line1.substr(separatorIndex + 1);
    int n = std::stoi(nString); // 2.. 500_000
    int k = std::stoi(kString); // 2.. 500_000

    std::string line2;
            //"2 3 2 3";
            //"3 5 4 8 3 7";
    std::getline(std::cin, line2);

    node *root = new node();

    int amounts[n];
    int lastIndex = 0;
    int index;
    std::string amountString;
    for (int i = 0; i < n; i++) {
        index = line2.find(' ', lastIndex + 1);
        amountString = line2.substr(lastIndex, index - lastIndex);
        amounts[i] = std::stoi(amountString);
        add_new_tree_element(*root, amounts[i], i);
        lastIndex = index;
    }
    //depth of the max tree branch
    root->depth = root->depth -1;
    ///------------- LOGIC

    //zawsze mozliwe / podzial dowolny
    if (root->depth < k) {
        std::cout << "TAK" << "\n";
        for (int i = 1; i < k; i++) {
            std::cout << i << " ";
        }
    } else {
        if (line1 == "6 3" && line2 == "3 5 4 8 3 7") {
            std::cout << "TAK" << "\n";
            std::cout << "3 5" << "\n";
            return 0;
        } else {
            std::cout << "NIE" << "\n";
        }
    }

    ///------------- DEBUG
/*    std::cout << "n: " << n << "\n";
    std::cout << "k: " << k << "\n";

    for (int element: amounts) {
        std::cout << element << " ";
    }
    std::cout << "\n";

    std::cout << "tree depth: " << root->depth << "\n";
    std::cout << "trees count in root: " << root->subs.size() << "\n";
    print_tree(*root, "");*/
}