Desafios de Programação no Verão de 2011 - Prova 07 - Equipe

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

Shortest Subchain (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <string.h>

using namespace std;

#define NMAX 131072

int tamanho[NMAX], pai[NMAX], pilha[NMAX];
int a[NMAX], atu[NMAX];

int main() {
	int n;
	scanf("%d", &n);
	memset(tamanho, -1, sizeof(tamanho));
	memset(pai, -1, sizeof(pai));
	memset(atu, -1, sizeof(atu));
	for (int i = 0; i < n; i++) {
		scanf("%d", a+i);
		if (i == 0) {
			tamanho[a[i]] = 0;
		} else {
			if (tamanho[a[i]] == -1 || tamanho[a[i-1]] + 1 < tamanho[a[i]]) {
				tamanho[a[i]] = tamanho[a[i-1]] + 1;
				pai[i] = i-1;
				atu[ a[i] ] = i-1;
			} else {
				pai[i] = atu[ a[i] ];
			}
		}
	}
	int x = n-1;
	int out = 0;
	while (x != -1) {
		pilha[out++] = a[x];
		x = pai[x];
	}
	printf("%d", pilha[out-1]);
	for (int i = out-2; i >= 0; i--) {
		printf(" %d", pilha[i]);
	}
	printf("\n");
	return 0;
}

Median (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
typedef unsigned long long llu;
#define NMAX 1000002

int n;
int A[NMAX];

int conta_pos(int val, int pos) {
	int ini = pos+1, fim = n-1, meio; 
	while(ini + 2 < fim) {
		meio = (ini + fim) / 2;
		int dif = A[meio] - A[pos];
		if(dif <= val) {
			ini = meio;
		} else {
			fim = meio;
		}
	}
	for(meio = fim; meio >= ini; meio--) {
		int dif = A[meio] - A[pos];
		if(val >= dif) return meio - pos;	
	}
	return 0;
}

long long conta(int val, long long &qtd) {
	long long s = 0;
	for(int i = 0; i < n; i++) {
		s += conta_pos(val, i);
		if(s >= qtd) return s;
	}
	return s;
}

int resolve(long long qtd) {
	unsigned ini = 0, fim = 2000000000, meio;
	while(ini + 2 < fim) {
		meio = (ini+fim) / 2;
		long long x = conta(meio, qtd);
		if(x >= qtd) {
			fim = meio;
		} else{
			ini = meio;
		}
	}
	for(meio = ini; meio <= fim; meio++) {
		if(conta(meio, qtd) >= qtd) {
			return meio;
		}
	}
	return fim+1;
}

int main() {
	while (scanf("%d", &n) != EOF) {
		for (int i = 0; i < n; i++) {
			scanf("%d", &A[i]);
		}
		sort(A, A+n);
		llu ideal = (((llu) n) * (llu)(n - 1)) / 2llu;
		printf("%d\n", resolve((ideal+1)/2));
	}
	return 0;
}

Bergamot Problem (por aWARush/)

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <utility>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>


using namespace std;
int N, M;
int group[22];
int cant[22];
int llenos;
int arr[55][2];
int G;
int paso = 1;
int seen[33][33];
bool done;
int check[14][55];
int tot[14];
bool doit(int ind)
{
	
	if( done ) return true;
	if( G-llenos > N-ind ) return false;
	if( ind == N )
	{
		paso ++ ;
		for( int i = 0 ; i < M ; i ++ )
		{
//			cout << group[arr[i][0]] << "  " << group[arr[i][1]] << endl;
			if( seen[group[arr[i][0]]][group[arr[i][1]]] == paso ) return false;
			seen[group[arr[i][0]]][group[arr[i][1]]] = paso;
		}
		done = true;
		return true;
	}
	
	for( int i = 0 ; i < G ; i ++ ) 
	{
		group[ind] = i;
		cant[i] ++;
		if( cant[i] == 1 ) llenos++;
		doit(ind+1);
		if( done ) return true;
		cant[i]--;
		if( cant[i] == 0 )
		{
			llenos--;
			break;
		}
	}
	return false;
}





int main()
{
	int i,j , k;
	cin >> N >> M;
	memset(arr, 0, sizeof(arr));
	memset(seen, 0, sizeof(seen));
	memset(tot, 0, sizeof(tot));
	
	for( i = 0 ; i < M ; i ++ )
	{
		string s; cin >> s;
		arr[i][0] = s[0]-'a';
		arr[i][1] = s[(int)s.size()-1]-'a';
	}
	
	int b = 0, e = N;
	while( b + 1 < e )
	{
		G = (e+b)/2;
		memset(cant, 0, sizeof(cant));
		llenos = 0;
		done = false;
		if( doit(0) )
		{
			e = G;
//			cout << "OK" << endl;
		}
		else
		{
//			cout << " FALSE " << G << endl;
			b = G;
		}
	}
	G = e;
	doit(0);
	cout << G << endl;
	int first = 1;
	for( i = 0 ; i < G ; i ++ )
	{
		bool ok = false;
		for( j = 0 ; j < N ; j ++ )
		{
			if( group[j] == i )
			{
				ok = true;
				char c = 'a' + j;
				cout << c;
			}
		}
		if( ok ) cout << endl;
	}
	return 0;
}

Hard Life (por Garotos da OBI)

#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstring>

#define INF 1000000000

#define MAXN 128
#define MAXM 1024
#define MAXS (2+MAXN+MAXM)

using namespace std;

int gcd(int a, int b)
{
	if (a == 0)
		return b;
	return gcd(b%a, a);
}

bool mycmp(const pair <int, int>& p1, const pair <int, int>& p2)
{
	return p1.first*p2.second < p1.second*p2.first;
}

int n, m;
vector <int> guys;
vector <pair <int, int> > edges;

int mark[MAXS];
vector <int> adj[MAXS];
int caps[MAXS][MAXS];

void dfs(int v)
{
	mark[v] = 1;

	if (1 <= v && v < 1+n)
		guys.push_back(v-1);

	for (int i = 0; i < (int)adj[v].size(); i++) {
		int v2 = adj[v][i];
		if (caps[v][v2] > 0 && !mark[v2])
			dfs(v2);
	}
}

int mindist[MAXS], queue[MAXS];
int augment(int v, int sink, int maxf)
{
	if (v == sink)
		return maxf;

	for (int i = 0; i < (int)adj[v].size(); i++) {
		int v2 = adj[v][i];
		if (mindist[v2] == mindist[v] + 1 && caps[v][v2] > 0) {
			int x = augment(v2, sink, min(maxf, caps[v][v2]));
			if (x) {
				caps[v][v2] -= x;
				caps[v2][v] += x;
				return x;
			}
		}
	}

	return 0;
}

int maxflow(int source, int sink)
{
	int flow = 0;

	do {
		int qs = 0, qe = 0;

		fill(mindist, mindist+MAXS, INF);

		mindist[source] = 0;
		queue[qe++] = source;
		
		while (qs < qe && mindist[sink] == INF) {
			int v = queue[qs++];
			for (int i = 0; i < adj[v].size(); i++) {
				int v2 = adj[v][i];
				if (caps[v][v2] > 0 && mindist[v2] > mindist[v] + 1) {
					mindist[v2] = mindist[v] + 1;
					queue[qe++] = v2;
				}
			}
		}

		if (mindist[sink] == INF)
			break;

		int temp = 0;
		int x;
		while (x = augment(source, sink, INF), x) {
			flow += x;
			temp += x;
		}
	} while (1);
		
	return flow;
}


int solve(int Ka, int Kb)
{
	memset(caps, 0, sizeof(caps));

	if (Ka == 0) {
		guys.clear();
		guys.push_back(0);
		return 1;
	}

	Ka *= 100, Kb *= 100;
	Ka -= 1;

	for (int i = 0; i < 2+n+m; i++)
		adj[i].clear();

	for (int i = 0; i < (int)edges.size(); i++) {
		int a = edges[i].first, b = edges[i].second;
		
		caps[0][1+n+i] = Kb;
		caps[1+n+i][0] = Kb;
		adj[0].push_back(1+n+i);
		adj[1+n+i].push_back(0);

		caps[1+n+i][1+a] = Kb;
		caps[1+a][1+n+i] = Kb;
		adj[1+a].push_back(1+n+i);
		adj[1+n+i].push_back(1+a);

		caps[1+n+i][1+b] = Kb;
		caps[1+b][1+n+i] = Kb;
		adj[1+b].push_back(1+n+i);
		adj[1+n+i].push_back(1+b);
	}

	for (int i = 0; i < n; i++) {
		caps[1+i][1+n+m] = Ka;
		caps[1+n+m][1+i] = Ka;
		adj[1+i].push_back(1+n+m);
		adj[1+n+m].push_back(1+i);
	}

	int flow = maxflow(0, 1+n+m);

	if (flow-m*Kb < 0) {
		memset(mark, 0, sizeof(mark));
		guys.clear();
		dfs(0);
		if (guys.empty())
			return 0;

		return 1;
	}

	return 0;
}

int main(int argc, char ** argv)
{
	int firstest = 1;
	
	while (scanf("%d %d", &n, &m) == 2) {
		edges.clear();

		for (int i = 0; i < m; i++) {
			int a, b;
			scanf("%d %d", &a, &b);
			a--, b--;

			edges.push_back(make_pair(a, b));
		}

		vector <pair <int, int > > Ks;

		for (int j = 1; j <= n; j++)
			for (int i = 0; i <= j*(j-1)/2; i++)
				if (gcd(i, j) == 1)
					Ks.push_back(make_pair(i, j));

		sort(Ks.begin(), Ks.end(), mycmp);

		guys.clear();

		int left = 0, right = Ks.size()-1;

		while (left < right) {
			int me = (left+right+1)/2;

			if (solve(Ks[me].first, Ks[me].second))
				left = me;
			else
				right = me-1;
		}

		solve(Ks[left].first, Ks[left].second);

		if (!firstest)
			printf("\n");

		sort(guys.begin(), guys.end());
		printf("%d\n", (int)guys.size());
		for (int i = 0; i < (int)guys.size(); i++)
			printf("%d\n", guys[i]+1);

		firstest = 0;
	}

	return 0;
}

Vasya Ferrari (por SUDO)

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define fori(i, n) for ( int i = 0; i < (n); ++i )
#define forr(i, a, b) for ( int i = (a); i <= (b); ++i )
#define ford(i, a, b) for ( int i = (a); i >= (b); --i )
#define tr(it, a, b) for ( typeof(a) it = (a); it != (b); ++it )
#define all(x) (x).begin(),(x).end()
#define sz size()
#define pb push_back

const int INF = 0x3F3F3F3F;

vector<int> factor(int x) {
	vector<int> fac;
	if( x == 0 ) {
		return fac;
	}
	if( x < 0 ) x = -x;
	
	fac.push_back(1);
	
	int sqn = (int)(sqrt((double)x)) + 1;
	
	forr(i,2,sqn) {
		if( x % i == 0 ) {
			fac.push_back(i);
		}
	}
	int start = fac.size()-2;
	if( fac[fac.size()-1]*fac[fac.size()-1] != x ) {
		fac.pb( x/fac[fac.size()-1] );
	}
	ford(i,start,0) {
		fac.pb( x/fac[i] );
	}
	
	return fac;
}

int trydiv(int &a, int &b, int &c, int &d, int k4) {
	if( d%k4 != 0 ) return 0;
	
	int k3 = d/k4;
	
	if( (c-k3)%k4 == 0 ) {
		int k2 = (c-k3)/k4;
		if( (b-k2)%k4 == 0 ) {
			int k1 = (b-k2)/k4;
			if( k1+k4 == a ) {
				a = k1;
				b = k2;
				c = k3;
				d = k4;
				return 1;
			}
		}
	}
	
	return 0;
}

int trydiv(int &a, int &b, int &c, int k3) {
	if( c%k3 != 0 ) return 0;
	
	int k2 = c/k3;
	
	if( (b-k2)%k3 == 0 ) {
		int k1 = (b-k2)/k3;
		if(k1+k3 == a) {
			a = k1;
			b = k2;
			c = k3;
			return 1;
		}
	}
	
	return 0;
}

int trydiv(int &a, int &b, int k2) {
	if( b%k2 != 0 ) return 0;
	
	int k1 = b/k2;
	
	if( a == k1+k2 ) {
		a = k1;
		b = k2;
		return 1;
	}
	
	return 0;
}

int trydiv2(int &a, int &b, int &c, int &d, int k2) {
	if( d%k2 != 0 ) return 0;
	
	int k4 = d/k2;
	int x = b-k2-k4;
	
	if( x != 0 ) {
	    vector<int> facx = factor(x);
	
	    fori(i,facx.size()) {
		    int k1 = facx[i];
		    int k3 = x/k1;
		
		    if( k1+k3 == a && (k1*k4+k2*k3)==c ) {
			    a = k1;
			    b = k2;
			    c = k3;
			    d = k4;
			    return 1;
		    }
		
		    k1 = -facx[i];
		    k3 = x/k1;
		
		    if( k1+k3 == a && (k1*k4+k2*k3)==c ) {
			    a = k1;
			    b = k2;
			    c = k3;
			    d = k4;
			    return 1;
		    }
	    }
	} else {
	    int k1 = a;
	    int k3 = 0;
	    if( (k1*k4+k2*k3)==c ) {
	        a = k1;
		    b = k2;
		    c = k3;
		    d = k4;
		    return 1;
	    }
	    
	    k1 = 0;
	    k3 = a;
	    if( (k1*k4+k2*k3)==c ) {
	        a = k1;
		    b = k2;
		    c = k3;
		    d = k4;
		    return 1;
	    }
	}
	return 0;
}

void printcoef(int a, string xx) {
	if( a > 0 ) {
		cout << "+";
		if( a != 1 ) cout << a;
		else if( xx == "" ) cout << a;
		cout << xx;
	}
	else if( a < 0 ) {
		cout << a;
		cout << xx;
	}
}

int main() {
	int a, b, c, d;
	while (cin >> a >> b >> c >> d ) {
	
	vector<int> facd = factor(d);
	int k1 = INF;
	if( d == 0 ) {
		k1 = 0;
	} else {
		fori(i,facd.size()) {
			if( trydiv(a, b, c, d, facd[i]) ) {
				k1 = facd[i];
				break;
			}
			if( trydiv(a, b, c, d, -facd[i]) ) {
				k1 = -facd[i];
				break;
			}
		}
	}
	
	int k2 = INF;
	if( k1 == INF ) {
		int fail = 1;
		fori(i,facd.size()) {
			if( trydiv2(a, b, c, d, facd[i]) ) {
				fail = 0;
				break;
			}
			if( trydiv2(a, b, c, d, -facd[i]) ) {
				fail = 0;
				break;
			}
		}
		if( fail ) {
			cout << "Irreducible" << endl;
		continue;
		}
		
		cout << "(x2";
		
		printcoef(a,string("x"));
		printcoef(b,string(""));
		
		cout << ")";
		cout << "(x2";
		
		printcoef(c,string("x"));
		printcoef(d,string(""));
		
		cout << ")" << endl;
				
		continue;
	} else {
		if( c == 0 ) {
			k2 = 0;
		} else {
			vector<int> facc = factor(c);
			fori(i,facc.size()) {
				if( trydiv(a, b, c, facc[i]) ) {
					k2 = facc[i];
					break;
				}
				if( trydiv(a, b, c, -facc[i]) ) {
					k2 = -facc[i];
					break;
				}
			}
		}
	}
	
	int k3 = INF;
	if( k2 == INF ) {
		cout << "(x3";
		
		printcoef(a,string("x2"));
		printcoef(b,string("x"));
		printcoef(c,string(""));
		
		cout << ")";
		cout << "(x";
		printcoef(k1,string(""));
		cout << ")" << endl;
		continue;
	} else {
		if( b == 0 ) {
			k3 = 0;
		}
		else {
			vector<int> facb = factor(b);
			fori(i,facb.size()) {
				if( trydiv(a, b, facb[i]) ) {
					k3 = facb[i];
					break;
				}
				if( trydiv(a, b, -facb[i]) ) {
					k3 = -facb[i];
					break;
				}
			}
		}
	}
	
	if( k3 == INF ) {
		cout << "(x2";
		
		printcoef(a,string("x"));
		printcoef(b,string(""));
		
		cout << ")";
		cout << "(x";
		printcoef(k1,string(""));
		cout << ")";
		
		cout << "(x";
		printcoef(k2,string(""));
		cout << ")" << endl;
		continue;
	}
	
	cout << "(x";
	printcoef(k1,string(""));
	cout << ")";
	
	cout << "(x";
	printcoef(k2,string(""));
	cout << ")";
	
	cout << "(x";
	printcoef(k3,string(""));
	cout << ")";
	
	cout << "(x";
	printcoef(a,string(""));
	cout << ")" << endl;
	}

	return 0;
}

Lunar Code 2 (por AUHAUAH Balões Mano)

#include <stdio.h>

#define MOD 1000000007LL

typedef long long ll;

ll fat[200001], invfatm[200001];

ll pot(ll b, int p)
{
	if(p == 0) return 1;
	ll r = pot(b, p/2);
	if(p%2) return (((r*r)%MOD)*b)%MOD;
	return (r*r)%MOD;
}

ll invfat(int p)
{
	if(invfatm[p]) return invfatm[p];
	return invfatm[p] = pot(fat[p], MOD-2);
}

ll comb(int n, int k)
{
	ll ret = (fat[n]*invfat(k))%MOD;
	return (ret*invfat(n-k))%MOD;
}

int main()
{
	ll n, m, k, l, sum = 0;
	scanf("%lld%lld%lld%lld", &m, &n, &k, &l);
	fat[0] = 1;
	for(ll i = 1; i <= m+n; i++)
		fat[i] = (fat[i-1]*i)%MOD;
	
	for(ll i = 0; i <= m-k; i++)
	{
		ll delta = (pot(pot(2, m-k-i)-1, n-l)*comb(m-k,i))%MOD;
		if(i%2)
		{
			sum = sum - delta;
			while(sum < 0) sum += MOD;
		}
		else
			sum = (sum+delta)%MOD;
	}
	sum = (sum*comb(m, k))%MOD;
	sum = (sum*comb(n, l))%MOD;
	printf("%lld\n", sum);
	return 0;
}

Tickets (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <iostream>
using namespace std;

#define FIM 18

pair<long long,int> pd[FIM][1180][172][2][2];

long long aa,bb,k;
int a[FIM], b[FIM];

int num[FIM];

pair<long long,int> resolve(int pos, int ac, int sum, int menor, int maior) {
	if(pos == FIM) {
//		printf("OPA:\n");
//		for(int i = 0; i < 20; i++) {
//			printf("%d", num[i]);
//		}
//		printf("\n");
		if(ac + sum >= k) {
			return make_pair(1, 0);
		} else {
			return make_pair(0, ac + sum);
		}
	} else {
		pair<long long, int> out = pd[pos][ac][sum][menor][maior];
		if(out.first != -1) return out;

		int ini, fim;
		if(!menor && !maior) {
			ini = a[pos];
			fim = b[pos];
		} else if(!menor) {
			ini = a[pos];
			fim = 9;
		} else if(!maior) {
			ini = 0;
			fim = b[pos];
		} else {
			ini = 0;
			fim = 9;
		}

//		if(pos == 18) {
//			printf(">>>>>>>>>>>>>>>>>>>>>>.POS = 18\n");
//			printf("%d %d\n", a[pos], b[pos]);
//			printf("ANT = %d, INI FIM = %d %d\n", 
//		}
		long long res = 0;
		long long acc = ac;
		for(int i = ini; i <= fim; i++) {
			num[pos] = i;
			pair<long long,int> p = resolve(pos+1, acc, sum + i, menor || (i > a[pos]), maior || i < b[pos]);
			res += p.first;
			acc = p.second;
		}

//		printf("PD %d %d %d %d %d = (%lld, %lld)\n", pos, ac, sum, menor, maior, res, acc);
		return pd[pos][ac][sum][menor][maior] = make_pair(res, acc);
	}
}

int main() {
	cin >> aa >> bb >> k;
	for(int i = 0; i < FIM; i++) {
		a[FIM-1-i] = (aa%10ll); aa /= 10ll;
		b[FIM-1-i] = (bb%10ll); bb /= 10ll;
	}

	memset(pd, -1, sizeof(pd));

	pair<long long,int> p = resolve(0, 0, 0, 0, 0);
	cout << p.first << endl;
}

Mr. X (por Garotos da OBI)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <climits>
#include <sstream>
#include <cstring>
#include <cassert>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#include <set>

#define INF (INT_MAX/3)
#define MAXS 100010

typedef long long lint;

using namespace std;

const lint P = 2147542447;
const lint base = 37LL;
lint A[MAXS];
lint basepow[MAXS+3];
lint hash[MAXS], hash2[MAXS];

bool areyousure(int left, int right)
{
	while (left < right) {
		if (A[left] != A[right])
			return false;
		left ++, right --;
	}
	
	return true;
}

int palim(int left, int right, int n)
{
	lint h1 = hash[right];
	if (left-1 >= 0)
		h1 = (h1 - hash[left-1] + P)%P;
	h1 = (h1 * basepow[n-left])%P;

	lint h2 = hash2[left];
	if (right+1 < n)
		h2 = (h2 - hash2[right+1] + P)%P;
	h2 = (h2 * basepow[right])%P;

	return (h1 == h2) && areyousure(left, right);
}

int possible(vector <int> poss, int n)
{
	int left = 0, right = n-1;

	fill(A, A+n, 11);

	for (int i = 0; i < (int)poss.size(); i++)
		A[poss[i]] = 17LL; /* Duplicated */

	hash[0] = A[0];
	for (int i = 1; i < n; i++)
		hash[i] = (hash[i-1] + basepow[i]*A[i])%P;

	hash2[n-1] = (A[n-1] * basepow[1])%P;
	for (int i = n-2; i >= 0; i--)
		hash2[i] = (hash2[i+1] + basepow[n-i]*A[i])%P;

	int found;
	do {
		found = 0;
		for (int s = 2; s <= right-left+1; s += 2) {
			if (palim(left, left+s-1, n)) {
				left += s/2;
				found = 1;
				break;
			}
			if (palim(right-s+1, right, n)) {
				right -= s/2;
				found = 1;
				break;
			}
		}
	} while (found);

	int many = 0;

	for (int i = left; i <= right; i++)
		if (A[i] == 17LL) /* Duplicated */
			many ++;
			
	return many <= 1;
}

int main(int argc, char ** argv)
{
	int nrow, ncol, k;
	map <int, vector <int> > cols, lines;

	scanf("%d %d %d", &nrow, &ncol, &k);

	if (k == 0) {
		printf("YES\n");
		return 0;
	}
	
	for (int i = 0; i < k; i++) {
		int y, x;
		scanf("%d %d", &y, &x);
		y--, x--;

		cols[x].push_back(y);
		lines[y].push_back(x);
	}

	int ok = 1;
	map <int, vector <int> >::iterator it, it2;

	for (it = cols.begin(), it2 = it, it2++; it2 != cols.end(); it++, it2++)
		if (it -> second != it2 -> second) {
			ok = 0;
			break;
		}

	if (ok) {
		for (it = lines.begin(), it2 = it, it2++; it2 != lines.end(); it++, it2++)
			if (it -> second != it2 -> second) {
				ok = 0;
				break;
			}
	}

	basepow[0] = 1;
	for (int i = 1; i <= max(ncol, nrow)+2; i++)
		basepow[i] = (base * basepow[i-1])%P;

	if (ok && possible(cols.begin()->second, nrow) && possible(lines.begin()->second, ncol))
		printf("YES\n");
	else
		printf("NO\n");

	return 0;
}

Berhatton (por AUHAUAH Balões Mano)

# include <cstdio>
# include <set>
# include <map>
# include <vector>
# include <cstring>
# include <algorithm>

# define MAXN 402000

using namespace std;

int arv[MAXN];
int maxIndice = (MAXN+2);
map<long long, long long> comp;
bool mrc[MAXN];

typedef long long ll;

struct PIZZA{
	ll d1, d2, w, low, up, id;
};

struct menor{
	inline bool operator() (const PIZZA &p1, const PIZZA &p2) const{
		if( p1.d1 != p2.d1) return p1.d1 < p2.d1;
		if( p1.d2 != p2.d2) return p1.d2 < p2.d2;
		return p1.id < p2.id;
	}
};

struct inic{
	inline bool operator() (const PIZZA &p1, const PIZZA &p2) const{
		if( (p1.d1 - p1.w) != (p2.d1 - p2.w) ) return (p1.d1-p1.w) < (p2.d1-p2.w);
		if( (p1.d1 + p1.w) != (p2.d1 + p2.w) ) return (p1.d1+p1.w) < (p2.d1+p2.w);
		return p1.id < p2.id;
	}
};

struct fim{
	inline bool operator() (const PIZZA &p1, const PIZZA &p2) const{
		if( (p1.d1 + p1.w) != (p2.d1 + p2.w) ) return (p1.d1+p1.w) < (p2.d1+p2.w);
		if( (p1.d1 - p1.w) != (p2.d1 - p2.w) ) return (p1.d1-p1.w) < (p2.d1-p2.w);
		return p1.id < p2.id;
	}
	
};

int acumula(int indice){
	int soma = 0;
	while(indice){
		soma += arv[indice];
		indice -= (indice & -indice);
	}
	return soma;
}

void update (int indice, int valor){
	while(indice <= maxIndice){
		arv[indice] += valor;
		indice += (indice & -indice);
	}
}

PIZZA pizza[MAXN];
set<ll> comprime;

int main (void){
	int n, k;
	ll x, y, w;
	scanf("%d%d", &n, &k);
	for(int i = 0 ; i < n; i++){
		scanf("%lld%lld%lld", &pizza[i].d1, &pizza[i].d2, &pizza[i].w);
		x = pizza[i].d1;
		y = pizza[i].d2;
		w = pizza[i].w;
		comprime.insert(x-y);
		comprime.insert(x-y+w);
		comprime.insert(x-y-w);
	}
	
	set<ll> :: iterator it;
	
	int cnt = 1;
	for(it = comprime.begin(); it != comprime.end(); ++it){
		comp[*it] = cnt++;
	}
	
	for(int i = 0; i < n; i++){
		x = pizza[i].d1;
		y = pizza[i].d2;
		w = pizza[i].w;
		pizza[i].d1 = (x+y);
		pizza[i].d2 = comp[x-y];
		pizza[i].low = comp[x-y-w];
		pizza[i].up = comp[x-y+w];
		pizza[i].id = i;
	}
	
	sort(pizza, pizza+n, menor());
	
	set<PIZZA, inic> head;
	set<PIZZA, fim> tail;
	
	for(int i = 0; i < n ; i++) head.insert(pizza[i]);
	int count = 0;
	memset(mrc, false, sizeof(mrc));
	for(int i = 0; i < n ; i++){	
		while( 1 ){
			if( tail.begin() == tail.end() ) break;
			PIZZA hut = *tail.begin();
			if( hut.d1 + hut.w < pizza[i].d1  ){
				tail.erase(hut);
				update(hut.low, -1);
				update(hut.up+1, 1);
			}
			else break;
		}
		
		while( 1 ){
			if( head.begin() == head.end() ) break;
			PIZZA hut = *head.begin();
			if( hut.d1 - hut.w <= pizza[i].d1  ){
				head.erase(hut);
				update(hut.low, 1);
				update(hut.up+1, -1);
				tail.insert(hut);
			}
			else break;
		}
		
		int s = acumula(pizza[i].d2);
	
		if( s > k ){
			count++;
			mrc[pizza[i].id] = true;
		}
	}
	printf("%d\n", count);
	for(int i = 0; i < n; i++){
		if( mrc[i] == true ){
			printf("%d ", i+1);
		}
	}
	printf("\n");
	return 0;
}