Home

Drogi użytkowniku internetu, witaj na mojej stronie!

Strona ta powstała, aby zebrać w jednym miejscu trochę moich przedsięwzięć i pokazać je światu. Trochę informacji dotyczących mojej osoby można przeczytać w zakładce O mnie. W kategoriach Informatyka, Matematyka oraz Muzyka znajdują się treści związane z tymi dyscyplinami. Osoby szukające ze mną kontaktu niech zaglądną na podstronę Kontakt. Na deser zostawiam jeszcze, moim zdaniem, ciekawe linki.

Miłego przeglądania!

Zobacz także cislo.net.pl

O mnie

Mam na imię Kuba i interesuję się informatyką, matematyką, muzyką oraz siatkówką.

Znam kilka języków programowania w różnym stopniu, m.in. C#, C++, Python czy Java. Na co dzień używam Linuksa - aktualnie jest to Manjaro (wersja ArchLinux) ze środowiskiem i3. Zajmuję się również algorytmiką. W zakładce Informatyka znajdziecie trochę moich programów i kodów. Fascynuje mnie również matematyka. Miałem przyjemność wygłosić kilka wykładów, więcej w zakładce Matematyka.

Poza tym grywam na różnych instrumentach, czasami komponuję. Więcej na podstronie Muzyka.

Informatyka

Poniżej linki do moich ostatnich małych projektów:

  • NeuralNetwork (Python) - Sieć nieuronowa ucząca się na zbiorze cyfr MNIST oraz zbiorze obrazków CIFAR-10.
  • Genetic knapsack for CUDA (C/C++, CUDA Driver API) - Implementacja genetycznego algorytmu dla problemu plecakowego przy użyciu technologii CUDA.
  • QuarterNote (Java) - Prosty program do tworzenia zapisu nutowego.
  • ChangeMaker [kod] (C#) - Program rozwiązujący problemy związane z wydawaniem reszty (jest to dodatek do wykładu).
  • MTUchanger (Java) - Aplikacja do automatycznej zmiany parametru MTU dla systemu Android.
  • Cubix.one.pl (Python, jQuery, HTML5, CSS3) - Prosty CMS stworzony z użyciem Pythona i mikroframeworka Flask.

Mała biblioteczka algorytmów (część z nich znajduje się na stronie Międzyszkolnego Olimpijskiego Kółka Informatycznego Kopernika):

Muzyka

Od 2 klasy szkoły podstawowej gram na keyboardzie (później trochę na fortepianie), uwielbiam perkusję, próbuję też swoich sił na gitarze. Ciągle chcę się uczyć grać na nowych instrumentach.

Swego czasu należałem do zespołu muzycznego ConCordia, z którym udało się nam wydać prywatnie płytę z kolędami i nie tylko.

Okładka

Wciąż muzykuję w różnym gronie :)

Różne kompozycje, nuty, mp3...

Błąd

Nie znaleziono strony...

Drzewo potęgowe

#include <cstdio>
const int MAX = 1000002;

int tree[MAX], x, y;
char c[10];

void update(int pos, int v)
{
	while(pos < MAX)
	{	
		tree[pos] += v;
		pos += (pos&-pos);
	}
}

int read(int pos)
{
	int r = 0;
	while(pos > 0)
	{
		r += tree[pos];
		pos -= (pos&-pos);
	}
	return r;
}

int main()
{
	while(scanf("%s", c) != EOF)
	{
		if(c[0] == 'U')
		{
			scanf("%d%d", &x, &y);
			update(x, y);
			printf("Updated\n");
		}
		else if(c[0] == 'R')
		{
			scanf("%d", &x);
			printf("%d\n", read(x));
		}
		else printf("Write only:\n*U x y - increase value of x position for y\n*R x - read sum values from 1 to x position\n\n Ctrl + d - quit\n");
	}
	return 0;
}

Słownik podsłów bazowych

Teoretycznie szybsza, lecz praktycznie wolniejsza implementacja.

/* 
   Copyright 2013 Jakub "Cubix651" Cisło
   Dictionary of base factors (DBF)
   Complexity: O(n log n + q log n)
   
   This algorithm is impractical, a better way is coding DBF
   using STL in complexity O(n log^2 n) - it's easier
   and the difference in speed is invisible.
*/
#include <cstdio>
#include <cstring>
#include <vector>
#define PB push_back
using namespace std;

const int MAXLEN = 500007, LOG = 30, SIGMA = 1000007;
int dbf[MAXLEN][LOG];

vector<vector<int> > countingSort(vector<vector<int> > tab, int size, int idx)
{
	vector<vector<int> > res;
	res.resize(size);
	for(int i = 0; i < size; ++i)
		res[i] = vector<int>();
	
	int cnt[SIGMA], tmp;
	for(int i = 0; i < SIGMA; ++i)
		cnt[i] = 0;
	for(int i = 0; i < size; ++i)
		++cnt[tab[i][idx]];
	for(int i = 1; i < SIGMA; ++i)
		cnt[i] += cnt[i-1];
	for(int i = SIGMA-1; i > 0; --i)
		cnt[i] = cnt[i-1];
	cnt[0] = 0;
	for(int i = 0; i < size; ++i)
		res[cnt[tab[i][idx]]++] = tab[i];
	return res;
}

vector<vector<int> > radixSort(vector<vector<int> > tab, int size, int k)
{
	for(int i = k-1; i >= 0; --i)
		tab = countingSort(tab, size, i);
	return tab;
}

void DBF(char *s, int size)
{
	for(int i = 0; i < size; ++i)
		dbf[i][0] = s[i]-'a';
	
	int len = 1, idx = 1;
	vector<vector<int> > vec;
	
	vec.resize(size);
	
	
	while(2*len <= size)
	{
		for(int i = 0; i + 2*len <= size; ++i)
		{
			vec[i] = vector<int>();
			vec[i].PB(dbf[i][idx-1]);
			vec[i].PB(dbf[i+len][idx-1]);
			vec[i].PB(i);
		}
		
		vec = radixSort(vec, size - 2*len + 1, 2);
		
		dbf[vec[0][2]][idx] = 0;
		for(int i = 1; i + 2*len <= size; ++i)
			dbf[vec[i][2]][idx] = dbf[vec[i-1][2]][idx] + ((vec[i][0]==vec[i-1][0] && vec[i][1]==vec[i-1][1])?0:1);
		
		++idx;
		len <<= 1;
	}
}

bool equal(int a, int b, int s)
{
	if(a == b || s == 0)
		return true;
	
	//this part can be preprocessed and complexity will O(n log n + q)
	int pow = 1, idx = -1;
	while(pow <= s)
	{
		pow <<= 1;
		++idx;
	}
	pow >>= 1;
	return ((dbf[a][idx] == dbf[b][idx]) && (dbf[a+s-pow][idx] == dbf[b+s-pow][idx]));
}

int main()
{
	char *str = "abbaabbabababbaaaba";
	DBF(str, strlen(str));
	printf("%s\n", equal(3, 15, 3) ? "tak" : "nie");
	printf("%s\n", equal(3, 15, 4) ? "tak" : "nie");
	return 0;
}

I na odwrót: teoretycznie wolniejsza, lecz praktycznie szybsza implementacja.

/* 
   Copyright 2013 Jakub "Cubix651" Cisło
   Dictionary of base factors (DBF)
   Complexity: O(n log^2 n + q log n)
*/
#include <cstdio>
#include <cstring>
#include <map>
#define MP make_pair
using namespace std;

const int MAXLEN = 500007, LOG = 30;
char str[MAXLEN];
int dbf[MAXLEN][LOG], n, q, x, y, divisor[MAXLEN], divPow[MAXLEN];


void DBF(char *s, int size)
{
	for(int i = 0; i < size; ++i)
		dbf[i][0] = s[i]-'a';
	
	int len = 1, idx = 1;
	map<pair<int, int>, int> M;
	
	while(2*len <= size)
	{
		for(int i = 0; i + 2*len <= size; ++i)
			M[MP(dbf[i][idx-1], dbf[i+len][idx-1])] = i;
		
		for(int i = 0; i + 2*len <= size; ++i)
			dbf[i][idx] = M[MP(dbf[i][idx-1], dbf[i+len][idx-1])];
		
		++idx;
		len <<= 1;
		M.clear();
	}
}

bool equal(int a, int b, int s)
{
	if(a == b || s == 0)
		return true;
	int pow = 1, idx = -1;
	while(pow <= s)
	{
		pow <<= 1;
		++idx;
	}
	pow >>= 1;
	return ((dbf[a][idx] == dbf[b][idx]) && (dbf[a+s-pow][idx] == dbf[b+s-pow][idx]));
}

int main()
{
	char* str = "abbaabbabababbaaaba";
	DBF(str, strlen(str));
	printf("%s\n", equal(3, 15, 3) ? "tak" : "nie");
	printf("%s\n", equal(3, 15, 4) ? "tak" : "nie");
	return 0;
}

Drzewo przedziałowe

Jeden z wariantów drzewa przedziałowego oznaczany (+, max).

/* 
   Copyright 2013 Jakub "Cubix651" Cisło
   Interval tree (interval - interval): (+, max)
   Add value for interval and ask about maximum value of interval
   Complexity: O(z log n)
*/

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 131074;
int n, m, z, p, k, l, W[MAX], M[MAX], S;

int greaterPow2(int x)
{
	int res = 1;
	while(res < x)
		res <<= 1;
	return res;
}

void insert(int a, int b, int c)
{
	a += S;
	b += S;
	
	W[a] += c;
	M[a] += c;
	if(a != b)
	{
		W[b] += c;
		M[b] += c;
	}
	
	while(a>>1 != b>>1)
	{
		if(!(a&1))
		{
			W[a+1] += c;
			M[a+1] += c;
		}
		if(b&1)
		{
			W[b-1] += c;
			M[b-1] += c;
		}
		
		a>>=1;
		b>>=1;
		
		M[a] = max(M[a<<1], M[(a<<1)+1]) + W[a];
		M[b] = max(M[b<<1], M[(b<<1)+1]) + W[b];
	}
	while(a != 1)
	{
		a>>=1;
		M[a] = max(M[a<<1], M[(a<<1)+1]) + W[a];
	}
}

int x, y;

int _query(int a, int b, int v, int sum)
{
	if(x <= a && b <= y)
		return sum + M[v];
	if(x > b || y < a)
		return 0;
	return max(
		_query(a, (a+b)/2, 2*v, sum+W[v]),
		_query((a+b)/2 + 1, b, 2*v+1, sum+W[v])
		);
}

int query(int a, int b)
{
	x = a;
	y = b;
	return _query(0, S-1, 1, 0);
}

void printTree()
{
	for(int i = 1; i <= 2*S; ++i)
		printf("(%d %d) ", W[i], M[i]);
	printf("\n\n");
}

/* Example: Task "Rails" (IX OI) */
int main()
{
	scanf("%d%d%d", &n, &m, &z);
	S = greaterPow2(n-1);
	while(z--)
	{
		scanf("%d%d%d", &p, &k, &l);
		--k;
		//printTree();
		if(query(--p, --k) + l <= m)
		{
			insert(p, k, l);
			printf("T\n");
		}
		else
		{
			printf("N\n");
		}
	}
	return 0;
}

Najniższy wspólny przodek

Algorytm Tarjana offline do znajdywania najniższego wspólnego przodka.

/* 
   Copyright 2013 Jakub "Cubix651" Cisło
   Solving Lowest Common Ancestor (LCA) problem offline.
   Tarjan's algorithm. Complexity: O(alpha(n) * n)
*/
#include <cstdio>
#include <vector>
using namespace std;

const int MAX = 1000000;
vector<int> graph[MAX], query[MAX], answer[MAX];
int n, q, x, y, rep[MAX], rank[MAX], anc[MAX];
short int visited[MAX]; //0 - not visited, 1 - visited 2 - processed

int Find(int a)
{
    if(rep[a] != a)
		rep[a] = Find(rep[a]);
	return rep[a];
}

void Union(int a, int b)
{
	a = Find(a);
	b = Find(b);
	if(a == b) return;
	
	if(rank[a] < rank[b])
		rep[a] = b;
	else if(rank[b] < rank[a])
		rep[b] = a;
	else
	{
		rep[a] = b;
		++rank[b];
	}
}

void MakeSets(int m)
{
	while(m--)
	{
		rep[m] = m;
		rank[m] = 0;
	}
}

void dfs(int v)
{
	visited[v] = 1;
	anc[v] = v;
	for(int i = 0; i < graph[v].size(); ++i)
	{
		if(visited[graph[v][i]] == 0)
		{
			dfs(graph[v][i]);
			Union(v, graph[v][i]);
			anc[Find(v)] = v;
		}
	}
	visited[v] = 2;
	for(int i = 0; i < query[v].size(); ++i)
	{
		if(visited[query[v][i]] == 2)
			answer[v][i] = anc[Find(query[v][i])];
	}
}

void LCA(int n, int root)
{
	MakeSets(n);
	for(int i = 1; i <= n; ++i)
		answer[i].resize(query[i].size());
	dfs(root);
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i < n; ++i)
	{
		scanf("%d%d", &x, &y);
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	scanf("%d", &q);
	while(q--)
	{
		scanf("%d%d", &x, &y);
		query[x].push_back(y);
		if(x!=y)
			query[y].push_back(x);
	}
	LCA(n, 1);
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 0; j < query[i].size(); ++j)
		{
			if(answer[i][j] != 0)
				printf("LCA(%d, %d) = %d\n", i, query[i][j], answer[i][j]);
		}
	}
	return 0;
}

Palindromy

Algorytm Manachera.

/* 
   Copyright 2013 Jakub "Cubix651" Cisło
   Finding all palindromes - Manacher's algorithm
   Complexity: O(n)
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 1000008;
int R[MAX];
void manacher(char* str, int len, int *R, bool o)
{
	char s[len+3];
	for(int i = 0; i < len; ++i)
	{
		s[i+1] = str[i];
		R[i] = 0;
	}
	R[len] = R[len+1] = R[len+2] = 0;
	s[0] = '#';
	s[len+1] = '$';
	s[len+2] = '\0';
	
	int i = 1, k = 1;
	while(i <= len)
	{
		while(s[i + R[i] + 1] == s[i - R[i] - o]) ++R[i];
		k = 1;
		for(k = 1; k <= R[i] && R[i-k] != R[i] - k; ++k)
			R[i+k] = min(R[i-k], R[i]-k);
		R[i+k] = max(min(R[i-k], R[i]-k), 0);
		i += k;
	}
}

int main()
{
	char* s = "aabbabbabbababababbbabaab";
	int len = strlen(s);
	for(int j = 0; j < 2; ++j)
	{
		manacher(s, len, R, j);
		for(int i = 1; i <= len; ++i)
			printf("%d ", R[i]);
		printf("\n");
	}
	return 0;
}

Ścieżka, cykl Hamiltona

Kody powstały podczas warsztatów Krajowego Funduszu na rzecz Dzieci.
Szukanie ścieżki i cyklu Hamiltona za pmocą rekurencji i programowania dynamicznego, jednak z wykorzystaniem dość dużej pamięci.

/*
	Copyright 2013 Jakub "Cubix651" Cisło
	Finding a hamiltonian path using recursion and dynamic programming
	Time complexity: O(2^n * n * m) = O*(2^n)
	Space complexity: O(2^n * n^2) = O*(2^n)
	Finding a hamiltonian cycle using hamiltonian paths
	Time complexity: O(2^n * n^3 * m) = O*(2^n)
	Space complexity: O(2^n * n^2) = O*(2^n)
*/
#include <cstdio>
#include <vector>
#define PB push_back
using namespace std;
typedef unsigned long long int LL;

const int MAX = 20;
int n, m;
vector<int> graph[MAX];
bool T[1<<MAX][MAX][MAX];

bool hamiltonianPath(LL W, int a, int b, int k)
{
	if(k == 0)
		return a == b;
	
	bool res = false;
	for(int i = 0; i < graph[a].size(); ++i)
	{
		if((1<<graph[a][i]) & W)
		{
			res = res || hamiltonianPath(W - (1<<graph[a][i]), graph[a][i], b, k-1);
		}
	}
	return res;
}

bool hasHamiltonianPathRec(int a, int b)
{
	return hamiltonianPath((1<<(n+1)) - 1, a, b, n-1);
}

/*	space complexity can be reduced by reducing table to T[2^(n+1)][n][2], 
	because we only use paths which length is k and k-1 */
bool hasHamiltonianPath(int a, int b)
{
	for(LL W = 1; W < (1<<(n+1)); ++W)
		for(int k = 0; k < n; ++k)
			for(int v = 0; v < n; ++v)
				T[W][v][k] = false;
	for(LL W = 1; W < (1<<(n+1)); ++W)
	{
		for(int k = 0; k < n; ++k)
		{
			for(int v = 0; v < n; ++v)
			{
				if(k == 0)
					T[W][v][0] = (v == b);
				else
				{
					for(int i = 0; i < graph[v].size(); ++i)
					{
						int c = graph[v][i];
						if((1<<c) & W)
						{
							T[W][v][k] = T[W][v][k] || T[W - (1<<graph[v][i])][graph[v][i]][k-1];
						}
					}
				}
			}
		}
	}
	return T[(1<<(n+1)) - 1][a][n-1];
}

vector<int> getHamiltonianPath(int v, int b)
{
	vector<int> res = vector<int>();
	//if(!hasHamiltonianPath(v, b))
	//	return res;
	res.PB(v);
	LL W = (1<<(n+1)) - 1 - (1<<v);
	int k = n-2;
	while(k>=0)
	{
		for(int i = 0; i < graph[v].size(); ++i)
			if(((1<<graph[v][i]) & W) && (T[W-(1<<graph[v][i])][graph[v][i]][k]))
			{
				v = graph[v][i];
				res.PB(v);
				W-=(1<<v);
				--k;
				break;
			}
	}
	return res;
}

vector<int> getHamiltonianCycle()
{
	vector<int> res = vector<int>();
	for(int a = 0; a < n; ++a)
	{
		for(int i = 0; i < graph[a].size(); ++i)
		{
			if(a != graph[a][i] && hasHamiltonianPath(a, graph[a][i]))
			{
				res = getHamiltonianPath(a, graph[a][i]);
				return res;
			}
		}
	}
	return res;
}

int main()
{
	scanf("%d%d", &n, &m);
	int x, y;
	while(m--)
	{
		scanf("%d%d", &x, &y);
		graph[--x].PB(--y);
		graph[y].PB(x);
	}
	vector<int> cycle = getHamiltonianCycle();
	if(cycle.size() == 0)
		printf("NIE\n");
	else
	{
		printf("TAK\n");
		for(int i = 0; i < cycle.size(); ++i)
			printf("%d ", cycle[i]+1);
		printf("\n");
	}
	return 0;
}

Poniższa implementacja redukuje wykorzystanie pamięci dzięki użyciu zasady włączeń i wyłączeń.

/*
	Copyright 2013 Jakub "Cubix651" Cisło
	Finding a hamiltonian cycle using inclusion-exclusion principle and dynamic programming
	Time complexity: O*(2^n)
	Space complexity: O(n^3) = O*(1)
*/

#include &lt;cstdio>
#include &lt;vector>
#define PB push_back
using namespace std;
typedef unsigned long long int LL;

const int MAX = 20;
int n, m;
vector&lt;int> graph[MAX];
LL T[MAX][MAX][MAX];

LL abs(int x)
{
	return (x &lt; 0?-x:x);
}

/*	space complexity can be reduced by reducing table to T[n][n][2], 
	because we only use rows k and k-1 */
LL tracksNumber(LL W)
{
	for(int k = 0; k &lt;= n; ++k)
		for(int a = 0; a &lt; n; ++a)
			for(int b = 0; b &lt; n; ++b)
				T[a][b][k] = 0;
	
	for(int k = 0; k &lt;= n; ++k)
	{
		for(int a = 0; a &lt; n; ++a)
		{
			for(int b = 0; b &lt; n; ++b)
			{
				if(k == 0)
					T[a][b][0] = ((a == b) && ((W & (1&lt;&lt;a)) != 0));
				else
				{
					for(int i = 0; i &lt; graph[a].size(); ++i)
					{
						if(((W & (1&lt;&lt;a)) != 0) && ((W & (1&lt;&lt;b)) != 0))
						{
							T[a][b][k] += T[graph[a][i]][b][k-1];
						}
					}
				}
			} 
		}
	}
	/*
	printf("____________________________\n%lld\n", W);
	
	for(int k = 0; k &lt;= n; ++k)
		for(int a = 0; a &lt; n; ++a)
			for(int b = 0; b &lt; n; ++b)
				if(T[a][b][k] != 0)
					printf("%d %d %d: %lld\n", a, b, k, T[a][b][k]);*/
	
	LL res = 0;
	for(int a = 0; a &lt; n; ++a)
		res += T[a][a][n];
	//printf("===%lld\n", res);
	return res;
}

bool hasHamiltonianCycle(int a, int b)
{
	//special case: graph [1]--[2]
	if(n == 2 && m == 1)
		return false;
	LL sub = 0;
	//#pragma omp parallel for
	for(LL W = 0; W &lt; (1&lt;&lt;n); ++W)
	{
		sub += tracksNumber(W) * ((((__builtin_popcountll(W))&1)&lt;&lt;1)-1);
	}
	return sub != 0;
}

int main()
{
	scanf("%d%d", &n, &m);
	int x, y;
	for(int i = 0; i &lt; m; ++i)
	{
		scanf("%d%d", &x, &y);
		if(x == y)
			continue;
		graph[--x].PB(--y);
		graph[y].PB(x);
	}
	if(hasHamiltonianCycle(--x, --y))
		printf("TAK\n");
	else
		printf("NIE\n");
	return 0;
}

Problem plecakowy

Kod również powstał na warsztatach KFnrD.
Implementacja algorytmu FPTAS.

/*
	Copyright 2013 Jakub "Cubix651" Cisło
	Knapsack problem - FPTAS
	Time complexity: O(n^3 / epsilon)
*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX = 100, MAXP = 10000, INF = 1000000007;
int n, P, b, c[MAX], w[MAX], T[MAX][MAX * MAXP];

int knapsack()
{
	for(int p = 0; p <= n*P; ++p)
		T[0][p] = INF;
	
	T[0][0] = 0;
	for(int i = 1; i <= n; ++i)
		for(int p = 0; p <= n*P; ++p)
		{
			T[i][p] = T[i-1][p];
			if(p - c[i] >= 0)
				T[i][p] = min(T[i][p], T[i-1][p-c[i]] + w[i]);
		}
	
	/*for(int i = 0; i <= n; ++i)
		for(int p = 0; p <= n*P; ++p)
			if(T[i][p] != INF)
				printf("%d %d: %d\n", i, p, T[i][p]);*/
	
	int res = 0;
	for(int p = 0; p <= n*P; ++p)
		if(T[n][p] <= b)
			res = max(res, p);
	return res;
}

int knapsackE(double E)
{
	double K = E * P / n;
	K = max(K, 1.0);
	for(int i = 1; i <= n; ++i)
		c[i] = int(double(c[i]) / K);
	P = int(double(P) / K) + 1;
	return K*knapsack();
}

int main()
{
	scanf("%d%d", &n, &b);
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d%d", &c[i], &w[i]);
		if(w[i] > b)
		{
			--i;
			--n;
			continue;
		}
		P = max(c[i], P);
	}
	double eps;
	scanf("%lf", &eps);
	printf("%d\n", knapsackE(eps));
	return 0;
}

Splay

Kod powstał podczas warsztatów Krajowego Funduszu na rzecz Dzieci.
Struktura danych pozwalająca szybko wstawiać, usuwać i wyszukiwać elementy.

/* 
   Copyright 2014 Jakub "Cubix651" Cis&#322;o
   Splay tree - self-balanced binary search tree
   Amortized complexity of query: O(log n)
*/
#include <cstdio>
#include <ctime>
#include <cstdlib>

template <typename T>
class Splay
{
	private:
	struct Node;
	Node *root;
	
	void Print(Node*);
	void rotate(Node*);
	void remove(T);
	void splay(Node*);
	Node* find(T);
	Node** where(Node*);

	public:
	Splay();
	~Splay();
	void Insert(T);
	void Remove(T);
	bool Find(T);	
	void Print();
};

template <typename T>
struct Splay<T>::Node
{
	Node *s[2];
	Node *parent;
	T val;
	Node(int v, Node* a, Node* b, Node* c)
	{
		val = v;
		parent = a;
		s[0] = b;
		s[1] = c;
	}
	~Node()
	{
		if(s[0]) delete s[0];
		if(s[1]) delete s[1];
	}
	bool isRight()
	{
		return (parent && parent->s[1] == this);
	}
};

template <typename T>
Splay<T>::Splay()
{
	root = NULL;
}

template <typename T>
Splay<T>::~Splay()
{
	if(root) delete root;
	root = NULL;
}

template <typename T>
typename Splay<T>::Node** Splay<T>::where(Node* v)
{
	if(v->parent == NULL)
		return &root;
	else
		return &(v->parent->s[v->isRight()]);
}

template <typename T>
void Splay<T>::rotate(Node* v)
{
	Node* p = v->parent, **z = where(p);
	bool right = v->isRight();
	p->s[right] = v->s[!right];
	if(p->s[right]) p->s[right]->parent = p;
	v->parent = p->parent;
	v->s[!right] = p;
	if(v->s[!right]) v->s[!right]->parent = v;
	(*z) = v;
}

template <typename T>
void Splay<T>::splay(Node* v)
{
	if(v == NULL) return;
	while(v->parent != NULL)
	{
		Node *p = v->parent;
		if(p->parent == NULL) //zig
			rotate(v);
		else
		{
			if(v->isRight() == p->isRight()) //zig-zig
			{
				rotate(p);
				rotate(v);
			}
			else //zig-zag
			{
				rotate(v);
				rotate(v);
			}
		}
	}
}

template <typename T>
void Splay<T>::Insert(T elem)
{
	Node **v = &root, *p = NULL;
	while((*v))
	{
		p = (*v);
		if(elem <= p->val)
			v = &p->s[0];
		else
			v = &p->s[1];
	}
	(*v) = new Node(elem, p, NULL, NULL);
	splay(*v);
}

template <typename T>
typename Splay<T>::Node* Splay<T>::find(T elem)
{
	Node *v = root, *last = NULL;
	while(v)
	{
		last = v;
		if(elem == v->val)
			break;
		if(elem < v->val)
			v = v->s[0];
		else
			v = v->s[1];
	}
	if(last) splay(last);
	return last;
}

template <typename T>
bool Splay<T>::Find(T elem)
{
	Node* tmp = find(elem);
	return (tmp && tmp->val == elem);
}

template <typename T>
void Splay<T>::remove(T elem)
{
	if(!root->s[0])
	{
		root = root->s[1];
		if(root) root->parent = NULL;
		return;
	}
	Node* prevRoot = root;
	root = root->s[0];
	while(root->s[1])
		root = root->s[1];
	prevRoot->s[0]->parent = NULL;
	splay(root);
	if(prevRoot->s[1]) prevRoot->s[1]->parent = root;
	root->s[1] = prevRoot->s[1];
	prevRoot->s[0] = prevRoot->s[1] = NULL;
	delete prevRoot;
}

template <typename T>
void Splay<T>::Remove(T elem)
{
	if(!Find(elem))
		return;
	remove(elem);
}

template <typename T>
void Splay<T>::Print(Node* start)
{
	if(!start)
		return;
	printf("%d %dn", start->val, start->isRight());
	Print(start->s[0]);
	Print(start->s[1]);
}

template <typename T>
void Splay<T>::Print()
{
	printf("DEBUG:n");
	Print(root);
}

int main()
{
	Splay<int> S;
	int c, n;
	while(scanf("%d%d", &c, &n) != EOF)
	{
		if(c == 0)
			S.Insert(n);
		else if(c == 1)
			S.Remove(n);
		else
			printf("%d", S.Find(n));
	}
	return 0;
}

Treap

Kod powstał podczas warsztatów Krajowego Funduszu na rzecz Dzieci.
Drzewiec/drzepiec - struktura danych pozwalająca szybko wstawiać, usuwać i wyszukiwać elementy.

/* 
   Copyright 2014 Jakub "Cubix651" Cis&#322;o
   Treap - randomized binary search tree, combination of BST and heap
   Average complexity of query: O(log n)
*/
#include <cstdio>
#include <ctime>
#include <cstdlib>

template <typename T>
class Treap
{
	private:
	static const int MAXPRIOR = 1000000007;
	struct Node;
	Node *root;
	
	void Print(Node*);
	void Insert(T, int);
	void rotate(Node*);
	void remove(Node*);
	Node *find(T);
	Node** where(Node*);

	public:
	Treap();
	~Treap();
	void Insert(T);
	void Remove(T);
	bool Find(T);	
	void Print();
	void Split(int, Treap**, Treap**);
	void Merge(int, Treap*, Treap*);
};

template <typename T>
struct Treap<T>::Node
{
	Node *s[2];
	Node *parent;
	int prior;
	T val;
	Node(int v, Node* a, Node* b, Node* c, int p)
	{
		val = v;
		prior = p;
		parent = a;
		s[0] = b;
		s[1] = c;
	}
	~Node()
	{
		if(s[0]) delete s[0];
		if(s[1]) delete s[1];
	}
	bool isRight()
	{
		return (parent && parent->s[1] == this);
	}
};

template <typename T>
Treap<T>::Treap()
{
	srand(time(NULL));
	root = NULL;
}

template <typename T>
Treap<T>::~Treap()
{
	if(root) delete root;
	root = NULL;
}

template <typename T>
typename Treap<T>::Node** Treap<T>::where(Node* v)
{
	if(v->parent == NULL)
		return &root;
	else
		return &(v->parent->s[v->isRight()]);
}

template <typename T>
void Treap<T>::rotate(Node* v)
{
	Node* p = v->parent, **z = where(p);
	bool right = v->isRight();
	p->s[right] = v->s[!right];
	if(p->s[right]) p->s[right]->parent = p;
	v->parent = p->parent;
	v->s[!right] = p;
	if(v->s[!right]) v->s[!right]->parent = v;
	(*z) = v;
}

template <typename T>
void Treap<T>::Insert(T elem, int pr)
{
	Node **v = &root, *p = NULL;
	while((*v))
	{
		p = (*v);
		if(elem < p->val)
			v = &p->s[0];
		else
			v = &p->s[1];
	}
	(*v) = new Node(elem, p, NULL, NULL, pr);
	p = (*v);
	while(p->parent && (p->prior > p->parent->prior))
		rotate(p);
}

template <typename T>
void Treap<T>::Insert(T elem)
{
	Insert(elem, rand() % MAXPRIOR);
}

template <typename T>
typename Treap<T>::Node* Treap<T>::find(T elem)
{
	Node *v = root;
	while(v)
	{
		if(elem == v->val)
			return v;
		if(elem < v->val)
			v = v->s[0];
		else
			v = v->s[1];
	}
	return NULL;
}

template <typename T>
bool Treap<T>::Find(T elem)
{
	return (find(elem) != NULL);
}

template <typename T>
void Treap<T>::remove(Node* v)
{
	if(!v) return;
	while(true)
	{
		if(v->s[0])
		{
			if(v->s[1])
				rotate(v->s[v->s[0]->prior < v->s[1]->prior]);
			else
				rotate(v->s[0]);
		}
		else
		{
			if(v->s[1])
				rotate(v->s[1]);
			else
			{
				(*where(v)) = NULL;
				delete v;
				return;
			}
		}
	}
}

template <typename T>
void Treap<T>::Remove(T elem)
{
	remove(find(elem));
}

template <typename T>
void Treap<T>::Split(int k, Treap** T1, Treap** T2)
{
	Insert(k, MAXPRIOR + 1);
	(*T1) = new Treap();
	(*T2) = new Treap();
	if(root->s[0]) root->s[0]->parent = NULL;
	if(root->s[1]) root->s[1]->parent = NULL;
	(*T1)->root = root->s[0];
	(*T2)->root = root->s[1];
	root->s[0] = NULL;
	root->s[1] = NULL;
	remove(root);
}

template <typename T>
void Treap<T>::Merge(int k, Treap* T1, Treap* T2)
{
	Insert(k, MAXPRIOR + 1);
	root->s[0] = T1->root;
	root->s[1] = T2->root;
	if(root->s[0]) root->s[0]->parent = root;
	if(root->s[1]) root->s[1]->parent = root;
	T1->root = NULL;
	T2->root = NULL;
	remove(root);
}

template <typename T>
void Treap<T>::Print(Node* start)
{
	if(!start)
		return;
	printf("%d %d %dn", start->val, start->prior, start->isRight());
	Print(start->s[0]);
	Print(start->s[1]);
}

template <typename T>
void Treap<T>::Print()
{
	printf("DEBUG:n");
	Print(root);
}

int main()
{
	Treap<int> T;
	int c, n;
	while(scanf("%d%d", &c, &n) != EOF)
	{
		if(c == 0)
			T.Insert(n);
		else if(c == 1)
			T.Remove(n);
		else
			printf("%d", T.Find(n));
	}
	return 0;
}