Hometown Newspaper

#include <bits/stdc++.h>
using namespace std;
void merge(int arr[], int start, int mid, int end){
    int left[mid-start+1]={0};
    int right[end-mid]={0};
    for(int i=start; i<mid+1; i++){
        left[i-start] =  arr[i];
    }
    for(int i=mid+1; i<=end; i++){
        right[i-(mid+1)] = arr[i];
    }
    int leftIndex=0, rightIndex=0, arrIndex=start;
    for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
        if(left[leftIndex]<right[rightIndex]){
            arr[arrIndex] = left[leftIndex++];
        }
        else{
            arr[arrIndex] = right[rightIndex++];
        }
    }

    while(leftIndex<=mid-start){
        arr[arrIndex++] = left[leftIndex++];
    }

    while(rightIndex<end-mid){
        arr[arrIndex++] = right[rightIndex++];
    }

}

void mergeSort(int arr[], int start, int end){
    if(end==start)
        return;
    mergeSort(arr,start,(start+end)/2);
    mergeSort(arr,((start+end)/2)+1,end);
    merge(arr,start,(start+end)/2,end);
}

int main()
{
  int test;
  cin>>test;

  while(test--){

    int n;
    cin>>n; 

    char news[n][99999];
    int popularityAway[99999];
    int popularityHome[99999];
    int indexing[999999] = {0};

    int home=0, away=0, temp;

    for(int i=0; i<n; i++){
      int val;
      cin>>news[i]>>temp>>val;
      if(val==1)
        popularityHome[home++] = temp;
      else
        popularityAway[away++] = temp;
      indexing[temp] = i;
    }
    if(away>0)
      mergeSort(popularityAway, 0, away-1);
    if(home>0)
      mergeSort(popularityHome, 0, home-1);

    if(home>0){
      for(int i=home-1 ;i>=0; i--)
        cout<<news[indexing[popularityHome[i]]]<<endl;
    }
    if(away>0){
      for(int i=away-1; i>=0; i--)
        cout<<news[indexing[popularityAway[i]]]<<endl;
    }
  }
}

import java.util.*;
import java.io.*;

public class Main {
  static void merge(int arr[], int start, int mid, int end){
    int left[] = new int[mid-start+1];
    int right[] = new int[end-mid];
    for(int i=start; i<mid+1; i++){
        left[i-start] =  arr[i];
    }
    for(int i=mid+1; i<=end; i++){
        right[i-(mid+1)] = arr[i];
    }
    int leftIndex=0, rightIndex=0, arrIndex=start;
    for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
        if(left[leftIndex]<right[rightIndex]){
            arr[arrIndex] = left[leftIndex++];
        }
        else{
            arr[arrIndex] = right[rightIndex++];
        }
    }

    while(leftIndex<=mid-start){
        arr[arrIndex++] = left[leftIndex++];
    }

    while(rightIndex<end-mid){
        arr[arrIndex++] = right[rightIndex++];
    }

  }

  static void mergeSort(int arr[], int start, int end){
      if(end==start)
          return;
      mergeSort(arr,start,(start+end)/2);
      mergeSort(arr,((start+end)/2)+1,end);
      merge(arr,start,(start+end)/2,end);
  }

  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int test = sc.nextInt();

    while(test--!=0){

      int n = sc.nextInt();

      String news[] = new String[n];
      int popularityAway[] = new int[99999];
      int popularityHome[] = new int[99999];
      int indexing[] = new int[999999];

      int home=0, away=0;

      for(int i=0; i<n; i++){
        news[i] = sc.next();
        int temp = sc.nextInt(),val = sc.nextInt();
        if(val==1)
          popularityHome[home++] = temp;
        else
          popularityAway[away++] = temp;
        indexing[temp] = i;
      }

      if(away>0)
        mergeSort(popularityAway, 0, away-1);
      if(home>0)
        mergeSort(popularityHome, 0, home-1);

      if(home>0){
        for(int i=home-1 ;i>=0; i--)
          System.out.println(news[indexing[popularityHome[i]]]);
      }
      if(away>0){
        for(int i=away-1; i>=0; i--)
          System.out.println(news[indexing[popularityAway[i]]]);
      }
    }

  }
}

def merge(arr, start, mid, end):

	left = [0 for i in range(mid - start + 1)]
	right = [0 for i in range(end - mid)]
	
	for i in range(start, mid + 1):
		left[i - start] =  arr[i]
	
	for i in range(mid + 1, end + 1):
		right[i - (mid + 1)] = arr[i]
	
	leftIndex = 0
	rightIndex = 0
	arrIndex = start
	
	while leftIndex <= mid - start and rightIndex < end - mid:
	
		if(left[leftIndex] < right[rightIndex]):
			arr[arrIndex] = left[leftIndex]
			leftIndex += 1
		
		else:
			arr[arrIndex] = right[rightIndex]
			rightIndex += 1
		
		arrIndex += 1
	
	while(leftIndex <= mid - start):
		arr[arrIndex] = left[leftIndex]
		leftIndex += 1
		arrIndex += 1
	
	while(rightIndex < end - mid):
		arr[arrIndex] = right[rightIndex]
		rightIndex += 1
		arrIndex += 1
	
def mergeSort(arr, start, end):
	if(end == start):
		return
	mergeSort(arr, start, (start + end) // 2)
	mergeSort(arr, ((start + end) // 2) + 1, end)
	merge(arr, start, (start + end) // 2, end)


for _ in range(int(input())):

	n = int(input())
	indexing = [0] * 999999
	news = []
	popularityAway = [0] * 99999
	popularityHome = [0] * 99999
	home, away = 0, 0

	for i in range(n):
		
		z, temp, val = input().split()
		temp, val = int(temp), int(val)
		news.append(z)

		if val == 1:
			popularityHome[home] = temp
			home += 1
		
		else:
			popularityAway[away] = temp
			away += 1
		
		indexing[temp] = i

	if away:
		mergeSort(popularityAway, 0, away - 1)

	if home:
		mergeSort(popularityHome, 0, home - 1)

	if home:
		
		for i in range(home - 1, -1, -1):
			print(news[indexing[popularityHome[i]]])

	if away:

		for i in range(away - 1, -1, -1):
			print(news[indexing[popularityAway[i]]])