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
128
129
130
131
132
133
134
135
136
137
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using std::vector;
using std::multiset;
using std::cout;
using std::endl;


int timeNow = 0;

struct Process final {
    int id;
    int begin, end, duration;

    int doneSoFar;

    int end_min_dur;

    Process(int id, int begin, int end, int duration) : id(id), begin(begin), end(end), duration(duration), doneSoFar(0) {
        end_min_dur = end-duration;
    }

    int left() const noexcept {
        return (duration - doneSoFar);
    }

    void calculateOneTick() noexcept {
        ++doneSoFar;
    }

    int canSkip() const noexcept {
        return end_min_dur + doneSoFar - timeNow;
    }

    bool canStart() const noexcept {
        return (this->begin <= timeNow);
    }

    bool finished() const noexcept {
        return (this->left() == 0);
    }

    bool operator<(const Process & rhs) const noexcept {
        return this->canSkip() < rhs.canSkip();
    }




};


bool compareBeginTime(const Process &a, const Process &b) noexcept {
    return a.begin > b.begin;
}

int processesNr, coresNr;
vector<Process> tooEarlyProcesses;
vector<Process> sortedProcesses;

int main() {
    scanf("%d%d", &processesNr, &coresNr);
    sortedProcesses.reserve(processesNr);
    tooEarlyProcesses.reserve(processesNr);

    for(int i = 0; i < processesNr; ++i) {
        int begin, end, duration;
        scanf("%d%d%d", &begin, &end, &duration);
        tooEarlyProcesses.emplace_back(Process(i, begin, end, duration));
    }

    std::sort(tooEarlyProcesses.begin(), tooEarlyProcesses.end(), compareBeginTime);

    timeNow = 0;
    timeNow = tooEarlyProcesses.rbegin()->begin;

    while(true) {
//        if (timeNow % 20000 == 0)
//            printf("Time: %d\n", timeNow);

        auto it = tooEarlyProcesses.rbegin();
        while (it != tooEarlyProcesses.rend() && it->canStart()) {
            sortedProcesses.push_back(*it);
            tooEarlyProcesses.pop_back();
            it = tooEarlyProcesses.rbegin();
//            cout << it->id << " can start at " << it->begin << endl;
//            cout << "left " << tooEarlyProcesses.size() << " processes to start" << endl;
        }

        for(auto x = sortedProcesses.begin(); x < sortedProcesses.end(); ++x) {
            if (x->finished()) {
//                cout << x->id << " has finished!" << endl;
                *x = *sortedProcesses.rbegin();
                --x;
//                std::swap(*x, *sortedProcesses.rbegin());
                sortedProcesses.pop_back();
            }
        }

        std::sort(sortedProcesses.begin(), sortedProcesses.end());

//        for(auto x = sortedProcesses.begin(); x < sortedProcesses.end(); ++x) {
//            cout << "process " << x->id << " (" << x->begin << ", " << x->end << ") done: " <<
//                 x->doneSoFar << " left: " << x->left() <<
//                 " priority: " << x->canSkip() << endl;
//        }

        if (sortedProcesses.size() == 0) {
            printf("TAK\n");
            return 0;
        }
        if (sortedProcesses[0].canSkip() < 0) {
//            cout << "Cant make " << sortedProcesses[0].id << " at time " << timeNow << endl;
            printf("NIE\n");
            return 0;
        }


        int core = 0;
        for(auto x = sortedProcesses.begin(); x < sortedProcesses.end(); ++x) {
//            cout << "executing process " << x->id << " on core " << core << endl;
            x->calculateOneTick();

            core++;
            if (core == coresNr)
                break;
        }

        ++timeNow;
    }

    printf("FAIL\n");
    return 0;
}