Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <algorithm>
- using namespace std;
- void merge_series (int **arr, int first, int last_1, int last_2, int *dubl, int *ind, int par)
- {
- int i = first;
- int j = last_1+1;
- int c = 0;
- for (c = first; c <= last_2; c++)
- if (j > last_2)
- dubl[c] = ind[i++];
- else if (i > last_1)
- dubl[c] = ind[j++];
- else if (arr[ind[i]][par] >= arr[ind[j]][par] && par == 1)
- dubl[c] = ind[i++];
- else if (arr[ind[i]][par] <= arr[ind[j]][par] && par == 2)
- dubl[c] = ind[i++];
- else dubl[c] = ind[j++];
- }
- void sort (int **arr, int first, int last, int *dubl, int *ind, int par)
- {
- int middle = (first + last)/2;
- if (first < middle)
- sort (arr, first, middle, dubl, ind, par);
- if (middle + 1 < last)
- sort (arr, middle+1, last, dubl, ind, par);
- merge_series (arr, first, middle, last, dubl, ind, par);
- for (int i = first; i <= last; i++)
- {
- ind[i] = dubl[i];
- }
- }
- int main ()
- {
- int n;
- int **arr, *ind, *dubl;
- cin >> n;
- arr = new int* [n];
- ind = new int [n];
- dubl = new int [n];
- for (int i=0; i<n; i++)
- arr[i] = new int [3];
- for (int i=0; i<n; i++)
- {
- arr[i][0] = i+1;
- ind[i] = i;
- for (int j=1; j<3; j++)
- cin >> arr[i][j];
- }
- sort (arr, 0, n-1, dubl, ind, 1);
- int index = 0, shet = 0, i = n-1;
- for (int i=0; i<n; i++)
- dubl[i] = 0;
- while(i > 0)
- {
- while (arr[ind[i]][1] == arr[ind[i-1]][1] && i > 0)
- {
- index++;
- i--;
- }
- shet = i+1;
- //cout << index << " " << shet << endl;
- if (index != 0)
- {
- sort (arr, shet-1, index+shet-1, dubl, ind, 2);
- index = 0;
- }
- i--;
- }
- for (int i=0; i<n; i++)
- cout << ind[i] + 1 << " ";
- }
Add Comment
Please, Sign In to add comment