fork download 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. struct BSTNode {
  9.     string key;
  10.     int value;
  11.     int left;
  12.     int right;
  13.  
  14.     BSTNode() : key(""), value(0), left(-1), right(-1) {}
  15. };
  16.  
  17. int insertNodeBST(vector<BSTNode>& tree, int rootIndex, const string& key, int& nextAvailableIndex) {
  18.     if (rootIndex == -1) {
  19.         if (nextAvailableIndex >= tree.size()) {
  20.             tree.resize(nextAvailableIndex + 1);
  21.         }
  22.         tree[nextAvailableIndex].key = key;
  23.         tree[nextAvailableIndex].value = 1;
  24.         return nextAvailableIndex++;
  25.     }
  26.  
  27.     if (key < tree[rootIndex].key) {
  28.         tree[rootIndex].left = insertNodeBST(tree, tree[rootIndex].left, key, nextAvailableIndex);
  29.     } else if (key > tree[rootIndex].key) {
  30.         tree[rootIndex].right = insertNodeBST(tree, tree[rootIndex].right, key, nextAvailableIndex);
  31.     } else {
  32.         tree[rootIndex].value++;
  33.     }
  34.     return rootIndex;
  35. }
  36.  
  37. void inOrderTraversalBST(const vector<BSTNode>& tree, int index, vector<pair<string, int>>& result) {
  38.     if (index != -1) {
  39.         inOrderTraversalBST(tree, tree[index].left, result);
  40.         result.push_back({tree[index].key, tree[index].value});
  41.         inOrderTraversalBST(tree, tree[index].right, result);
  42.     }
  43. }
  44.  
  45. bool slt(string x, string y)
  46. {
  47. 	if (x.size() == y.size())
  48. 		return (x < y);
  49. 	return (x.size() < y.size());
  50. }
  51.  
  52. bool comparePairs(const pair<string, int>& a, const pair<string, int>& b) {
  53.     if (a.second != b.second) {
  54.         return (a.second > b.second);
  55.     }
  56.     return slt(a.first, b.first);
  57. }
  58.  
  59. int partition(vector<pair<string, int>>& a, int left, int right) {
  60.     pair<string, int> pivot = a[right];
  61.     int id = left - 1;
  62.     for (int i = left; i < right; i++) {
  63.         if (comparePairs(a[i], pivot)) {
  64.             id++;
  65.             swap(a[id], a[i]);
  66.         }
  67.     }
  68.     id++;
  69.     swap(a[id], a[right]);
  70.     return id;
  71. }
  72.  
  73. void quickSort(vector<pair<string, int>>& a, int left, int right) {
  74.     if (left < right) {
  75.         int pivot_index = partition(a, left, right);
  76.         quickSort(a, left, pivot_index - 1);
  77.         quickSort(a, pivot_index + 1, right);
  78.     }
  79. }
  80.  
  81. int main() {
  82.     ios_base::sync_with_stdio(false);
  83.     cin.tie(nullptr);
  84.     cout.tie(nullptr);
  85.  
  86.     int n;
  87.     cin >> n;
  88.     cin.ignore();
  89.  
  90.     vector<BSTNode> tree(n); // Kích thước tối đa
  91.     int rootIndex = -1;
  92.     int nextAvailableIndex = 0;
  93.  
  94.     for (int i = 0; i < n; ++i) {
  95.         string x;
  96.         cin >> x;
  97.         rootIndex = insertNodeBST(tree, rootIndex, x, nextAvailableIndex);
  98.     }
  99.  
  100.     vector<pair<string, int>> SortedResult;
  101.     inOrderTraversalBST(tree, rootIndex, SortedResult);
  102.  
  103.     quickSort(SortedResult, 0, SortedResult.size() - 1);
  104.  
  105.     for (const auto& p : SortedResult) {
  106.         cout << p.first << ' ' << p.second << '\n';
  107.     }
  108.  
  109. 	//cout << slt("3", "123");
  110.     return 0;
  111. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
10

123

123444

123444

12

1

8

1

455

455

9
stdout 
1 2
455 2
123444 2
8 1
9 1
12 1
123 1
https://ideone.com/o9GUWo
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!