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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

int taskNo, procNo;
int StartTime[100];
int EndTime[100];
int ExeTime[100];
int Margin[100];//zapas czasu który task moze poczekaæ

list<int> ProcessStart[1000001]; //czas kiedy proces moze siê zacz¹æ
list<int> EndMargin[1000001];//czas kiedy proces musi sie juz liczyæ
list<int> ProcessEnd[1000001];//czas kiedy proces siê skoñczy

list<int> Processed;//list obecnie liczonych zadañ posortowana od tego który mo¿e poczekaæ najd³u¿ej do tego który nie mo¿e czkeaæ
list<int> AwaitingTask;//lista oczekuj¹cych zadañ w kolejnoœci od tego co musi wczesniej wystartowac

void AddTaskToAwait(int taskId);
void RemoveTaskFromAwait(list<int>::iterator taskIt);
void AddTaskToProcessed(int taskId);
void RemoveTaskFromProcessed(list<int>::iterator taskIt);
void StartTask(list<int>::iterator taskIt, int time);
void StopTask(list<int>::iterator taskIt, int time);
int CalculateMarginForAwaitingTask(int taskId, int time);
bool SimulateProcessing();
void AddProcessEndTime(int taskId, int time);
void RemoveProcessEndTime(int taskId, int time);

int main()
{
   cin>>taskNo>>procNo;

   for(int i = 0; i < taskNo; i++)
   {
      cin>>StartTime[i];
      cin>>EndTime[i];
      cin>>ExeTime[i];
      Margin[i] = EndTime[i] - StartTime[i] - ExeTime[i];
      ProcessStart[StartTime[i]].push_back(i);
   }

   if(SimulateProcessing())
      cout<<"TAK";
   else
      cout<<"NIE";

   return 0;
}

bool SimulateProcessing()
{
   int taskFinished = 0;
   for(int time = 0; time < 1000001; time++)
   {
      if(taskFinished == taskNo)
         return true;

      //dla kazdego procesu który mo¿e sie teraz zacz¹æ
      for(list<int>::iterator StartIt = ProcessStart[time].begin(); StartIt != ProcessStart[time].end(); StartIt++)
         AddTaskToAwait(*StartIt);

      for(list<int>::iterator EndIt = ProcessEnd[time].begin(); EndIt != ProcessEnd[time].end(); EndIt++)
      {
         RemoveTaskFromProcessed(find(Processed.begin(), Processed.end(), *EndIt));
         taskFinished++;
      }

      while(AwaitingTask.size() > 0 && (Processed.size() < procNo || CalculateMarginForAwaitingTask(AwaitingTask.front(), time) < Margin[Processed.front()]))
      {
         StartTask(AwaitingTask.begin(), time);
      }

      if(AwaitingTask.size() > 0 && CalculateMarginForAwaitingTask(AwaitingTask.front(), time) == 0)
         return false;
   }
   return false;
}

void StartTask(list<int>::iterator taskIt, int time)
{
   //wstawiamy do listy procesowanych
   //RemoveEndMargin(taskId, time);
   int taskId = *taskIt;

   Margin[taskId] = CalculateMarginForAwaitingTask(taskId, time);//poprawiamy margin, bo przeszlismy ileœ w czasie gdy nie mielismy uruchomionego taska
   AddProcessEndTime(taskId, time);

   RemoveTaskFromAwait(taskIt);
   AddTaskToProcessed(taskId);

   if(Processed.size() > procNo) //usuwamy task najmniej istotny, czyli na pozycji zerowej, i go zatrzymujemy
      StopTask(Processed.begin(), time);
}

void StopTask(list<int>::iterator taskIt, int time)
{
   int taskId = *taskIt;

   ExeTime[taskId] = EndTime[taskId] - time - Margin[taskId];
   RemoveProcessEndTime(taskId, time);

   RemoveTaskFromProcessed(taskIt);
   AddTaskToAwait(taskId);

   //if(Margin[taskId] == 0)//nie mo¿na zatrzymaæ taska i przenieœc do await
   //AddEndMargin
}


void AddProcessEndTime(int taskId, int time)
{
   int endTime = time + ExeTime[taskId];
   ProcessEnd[endTime].push_back(taskId);
}

void RemoveProcessEndTime(int taskId, int time)
{
   int endTime = time + ExeTime[taskId];
   ProcessEnd[endTime].remove(taskId);
}

/*
void RemoveEndMargin(int taskId, int time)
{
   if(time == StartTime[taskId]) //jezeli staturjemy z powodu osi¹gniacia czasu startu taska
      return;

   int EndMarginTime = EndTime[taskId] - ExeTime[taskId];

   if(time == EndMarginTime) //jezeli startujemy, bo task musi wystartowaæ, to nie ma sensu go usuwaæ bo ju¿ go tam przetwarzamy i do niego nie wrócimy
      return;

   EndMargin[EndMarginTime].remove(taskId); //je¿eli startujemy bo inny task skoñczy³ swoje zadanie
}*/



void AddTaskToAwait(int taskId)
{
   for(list<int>::iterator it = AwaitingTask.begin(); it != AwaitingTask.end(); it++)
   {
      if(CalculateMarginForAwaitingTask(*it, 0) >= CalculateMarginForAwaitingTask(taskId, 0))
      {
         AwaitingTask.insert(it, taskId);
         return;
      }
   }

   AwaitingTask.push_back(taskId);
}

void RemoveTaskFromAwait(list<int>::iterator taskIt)
{
   AwaitingTask.erase(taskIt);
}

void RemoveTaskFromProcessed(list<int>::iterator taskIt)
{
   Processed.erase(taskIt);
}

void AddTaskToProcessed(int taskId)
{
   for(list<int>::iterator it = Processed.begin(); it != Processed.end(); it++)
   {
      if(Margin[*it] <= Margin[taskId]) //wstawiamy tutaj task
      {
         Processed.insert(it, taskId);
         return;
      }
   }

   Processed.push_back(taskId);
}

int CalculateMarginForAwaitingTask(int taskId, int time)
{
   return EndTime[taskId] - time - ExeTime[taskId];
}