Cod sursa(job #2562554)

Utilizator radustn92Radu Stancu radustn92 Data 29 februarie 2020 15:33:10
Problema Nums Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.75 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct stringWrapper {
	string wrappedString;

	stringWrapper() {}

	stringWrapper(string& s) {
		wrappedString = s;
	}

	bool operator < (const stringWrapper& other) const {
		if (wrappedString.size() < other.wrappedString.size()) {
			return true;
		} else if (wrappedString.size() > other.wrappedString.size()) {
			return false;
		}
		return wrappedString < other.wrappedString;
	}

	bool operator == (const stringWrapper& other) const {
		if (wrappedString.size() != other.wrappedString.size()) {
			return false;
		}
		return wrappedString == other.wrappedString;
	}
};

struct query {
	int opType;
	int key;
	stringWrapper s;
	int K;
};
vector<query> queries;
vector<stringWrapper> strings;
int totalOps;

struct node {
	int key;
	int priority;
	int size;

	node* leftChild;
	node* rightChild;

	node() {}

	node(int _key) {
		key = _key;
		priority = rand();
		leftChild = rightChild = NULL;
	}
};
typedef node* pnode;

int getSize(pnode node) {
	if (node == NULL) {
		return 0;
	}
	return 1 + getSize(node -> leftChild) + getSize(node -> rightChild);
}

void updateSize(pnode node) {
	if (node != NULL) {
		node -> size = getSize(node);
	}
}

pair<pnode, pnode> split(pnode root, int key) {
	if (root == NULL) {
		return {NULL, NULL};
	}
	if (key < root -> key) {
		pair<pnode, pnode> leftSplit = split(root -> leftChild, key);
		root -> leftChild = leftSplit.second;
		updateSize(root);
		return {leftSplit.first, root};
	}
	pair<pnode, pnode> rightSplit = split(root -> rightChild, key);
	root -> rightChild = rightSplit.first;
	updateSize(root);
	return {root, rightSplit.second};
}

pnode merge(pnode leftTree, pnode rightTree) {
	if (leftTree == NULL || rightTree == NULL) {
		return (leftTree == NULL) ? rightTree : leftTree;
	}

	if (leftTree -> priority > rightTree -> priority) {
		leftTree -> rightChild = merge(leftTree -> rightChild, rightTree);
		updateSize(leftTree);
		return leftTree;
	}
	rightTree -> leftChild = merge(leftTree, rightTree -> leftChild);
	updateSize(rightTree);
	return rightTree;
}

pnode search(pnode root, int key) {
	if (root == NULL || root -> key == key) {
		return root;
	}
	if (key < root -> key) {
		return search(root -> leftChild, key);
	}
	return search(root -> rightChild, key);
}

pnode insert(pnode root, pnode toInsert) {
	if (root == NULL) {
		return toInsert;
	}
	if (toInsert -> priority > root -> priority) {
		pair<pnode, pnode> splitByInsertionKey = split(root, toInsert -> key);
		toInsert -> leftChild = splitByInsertionKey.first;
		toInsert -> rightChild = splitByInsertionKey.second;
		updateSize(toInsert);
		return toInsert;
	}
	if (toInsert -> key < root -> key) {
		root -> leftChild = insert(root -> leftChild, toInsert);
	} else {
		root -> rightChild = insert(root -> rightChild, toInsert);
	}
	updateSize(root);
	return root;
}

pnode insert(pnode root, int key) {
	pnode prevNode = search(root, key);
	if (prevNode == NULL) {
		root = insert(root, new node(key));
	}
	return root;
}

pnode findKth(pnode root, int K) {
	if (root == NULL) {
		return NULL;
	}

	int currNodeIdx = getSize(root -> leftChild) + 1;
	if (K == currNodeIdx) {
		return root;
	} else if (K < currNodeIdx) {
		return findKth(root -> leftChild, K);
	}
	return findKth(root -> rightChild, K - currNodeIdx);
}

void debug(pnode root) {
	if (root == NULL) {
		return;
	}
	debug(root -> leftChild);
	stringWrapper sw = strings[root -> key];
	cout << sw.wrappedString << " ";
	debug(root -> rightChild);
}

void preProcessQueries() {
	cin >> totalOps;
	strings.reserve(totalOps);
	queries.reserve(totalOps);
	for (int opIdx = 0; opIdx < totalOps; opIdx++) {
		query query;
		cin >> query.opType;
		if (query.opType == 1) {
			string newString;
			cin >> newString;
			stringWrapper wrapper(newString);
			query.s = wrapper;
			strings.push_back(wrapper);
		} else {
			cin >> query.K;
		}
		queries.push_back(query);
 	}

 	sort(strings.begin(), strings.end());
 	strings.erase(unique(strings.begin(), strings.end()), strings.end());

 	for (int opIdx = 0; opIdx < totalOps; opIdx++) {
 		if (queries[opIdx].opType == 1) {
 			queries[opIdx].key = lower_bound(strings.begin(), strings.end(), queries[opIdx].s) - strings.begin();
 		}
 	}
}

int main() {
	freopen("nums.in", "r", stdin);
	freopen("nums.out", "w", stdout);

	srand(time(0));

	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	preProcessQueries();

	// pnode root = NULL;
	// for (int opIdx = 0; opIdx < totalOps; opIdx++) {
	// 	if (queries[opIdx].opType == 1) {
	// 		root = insert(root, queries[opIdx].key);
	// 	} else {
	// 		pnode kThElement = findKth(root, queries[opIdx].K);
	// 		stringWrapper sw = strings[kThElement -> key];
	// 		cout << sw.wrappedString << "\n";
	// 	}
	// }
	return 0;
}