Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <string.h>
- #include <math.h>
- #include <stdlib.h>
- // @author: Simran Singh 1816410280
- struct node {
- int f;
- char c;
- struct node *left;
- struct node *right;
- };
- void swap(struct node *a, struct node *b) {
- struct node temp = *a;
- *a = *b;
- *b = temp;
- }
- struct node* nodeFromTwo(struct node *a, struct node *b) {
- struct node* node = (struct node*)calloc(1, sizeof(struct node));
- node->f = a->f + b->f;
- node->c = '*';
- node->left = a;
- node->right = b;
- //printf("Summing %c %c = %d\n", a->c, b->c, node->f);
- return(node);
- }
- char cMap[26][100], sMap[26][100];
- void createMap(struct node *n, char *str) {
- if(n->left == NULL) {
- if(n->c >= 65 && n->c <= 65+26)
- strcpy(cMap[n->c - 65], str);
- else
- strcpy(sMap[n->c - 97], str);
- return;
- }
- char *left = (char*)malloc(26*sizeof(char));
- char *right = (char*)malloc(26*sizeof(char));
- strcpy(left, str);
- strcpy(right, str);
- int len = strlen(str);
- left[len] = '0';
- right[len] = '1';
- left[len+1] = '\0';
- right[len+1] = '\0';
- free(str);
- //printf("%c\n",n->c);
- createMap(n->left, left);
- createMap(n->right, right);
- }
- int main() {
- int n, q, i, j, qtype[9], sum = 0;
- struct node cache[100], *temp;
- char queries[9][1501];
- scanf("%d %d", &n, &q);
- for(i = 0; i < n; i++) {
- scanf("\n%c %d", &cache[i].c, &cache[i].f);
- sum += cache[i].f;
- cache[i].left = NULL;
- cache[i].right = NULL;
- }
- for(i = 0; i < q; i++) {
- scanf("%d %s", qtype + i, queries[i]);
- }
- for(i = 0; i < n; i++) {
- for(j = 0; j < n-i-1; j++) {
- if(cache[j].f > cache[j+1].f) {
- swap(&cache[j], &cache[j+1]);
- }
- }
- }
- for(i = 0; i < n; i+=2) {
- temp = nodeFromTwo(&cache[i], &cache[i+1]);
- if(temp->f == sum)
- break;
- j = n-1;
- while(cache[j].f >= temp->f){
- cache[j+1] = cache[j];
- j--;
- }
- cache[j+1] = *temp;
- n++;
- }
- struct node *root = temp;
- char *str = (char*)malloc(sizeof(char));
- str[0] = '\0';
- char c;
- createMap(temp, str);
- for(i = 0; i < q; i++) {
- j = 0;
- if(qtype[i] == 1) {
- c = *(queries[i] + j);
- while(c != '\0') {
- if(c >= 65 && c <= 65+26)
- printf("%s", cMap[c - 65]);
- else
- printf("%s", sMap[c - 97]);
- j++;
- c = *(queries[i] + j);
- }
- printf("\n");
- }
- else {
- c = *(queries[i] + j);
- temp = root;
- while(c != '\0') {
- if(temp->left != NULL) {
- if(c == '0')
- temp = temp->left;
- else
- temp = temp->right;
- }
- if(temp->left == NULL) {
- printf("%c", temp->c);
- temp = root;
- }
- j++;
- c = *(queries[i] + j);
- }
- printf("\n");
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement