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
#include <cstdio>

int pocz[128];
int konc[128];
int czas[128];
int vals[128];

int n,m,i,j,k,tasks,nextpocz,lasti,iter;

int acttasks[128],tskcount=0;
int nextsteptasks[128],nextsteps=0,np,nk;

inline void obnizAll(){ // aktualizuj cyferki jak dojdzie nowy mipek
	for(j=0;j<tskcount;j++){
		vals[acttasks[j]]-=(iter-lasti);
	}
	lasti=iter;
}

void addTasks(){
//			printf("================ AddT \n");
	obnizAll();
	// przelec i dodaj nowe do struktury
	nextpocz=1000000000;
	for(j=0;j<n;j++){
		nextpocz = pocz[j]>iter && pocz[j]<nextpocz ? pocz[j]:nextpocz;
		if(pocz[j]==iter){
//			printf("================ Addnew : %d \n",j);
			vals[j]=konc[j]-iter-czas[j];
//			printf("=%d  = %d - %d - %d \n",tskcount,konc[j],iter,czas[j]);
			// ustaw na dobrym miejscu
			k=tskcount;
			// wstaw od konca
			while( k>0 && vals[acttasks[k-1]]>konc[j]-iter-czas[j] ){
				acttasks[k]=acttasks[k-1];
				k--;
			}
			acttasks[k]=j;
			tskcount++;
		}
	}
//			printf("================ Nextpocz : %d \n",nextpocz);
}

int main(){
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++){
		scanf("%d%d%d",&pocz[i],&konc[i],&czas[i]);
	}
	tasks=n;
	nextpocz=0;
	lasti=0;
	for(iter=0;tasks>0;iter++){
	//		printf("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!================ iter = %d\n",iter);
		if(nextpocz==iter){
			addTasks();
		}
		// algorytm
		// zrob tyle ile procesorow
		
//		for(i=0;i<tskcount;i++){
//			printf("%d] %d %d\n",i,acttasks[i],vals[acttasks[i]]);
//		}

		for(i=0;i<m && i<tskcount;i++){
			vals[acttasks[i]]++;
			czas[acttasks[i]]--;
		}
		//wywal skonczone i scal tablice
		nextsteps=tskcount;
		np=0;nk=i;nextsteps=0;
		// scal 1 krok
		while (np < i && nk < tskcount){
				if (vals[acttasks[np]] < vals[acttasks[nk]]){
					nextsteptasks[nextsteps] = acttasks[np];
					np++;
				}
				else{
					nextsteptasks[nextsteps] = acttasks[nk];
					nk++;
				}
				// wywal jesli trzeba
				if(czas[nextsteptasks[nextsteps]]==0){ // zrobiony
					tasks--;
				}
				else
					nextsteps++;
		}
		if (np < i){
			while (np < i){
				nextsteptasks[nextsteps] = acttasks[np];
				np++;
				if(czas[nextsteptasks[nextsteps]]==0){ // zrobiony
					tasks--;
				}
				else
					nextsteps++;
			}
		}
		else{
			while (nk < tskcount){
				nextsteptasks[nextsteps] = acttasks[nk];
				nk++;
				if(czas[nextsteptasks[nextsteps]]==0){ // zrobiony
					tasks--;
				}
				else
					nextsteps++;
			}
		}
		for(i=0;i<nextsteps;i++){
			acttasks[i]=nextsteptasks[i];
		}
		tskcount=nextsteps;
		// koniec scalania
		if(tskcount>0 && konc[acttasks[0]]-(iter+1)-czas[acttasks[0]]<0)break;	
	}
	if(tasks==0)
		printf("TAK");
	else
		printf("NIE");
}