Created
October 19, 2014 20:20
-
-
Save sparfenyuk/75b665a9adc18fe6e96e to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <vector> | |
| #include <deque> | |
| #include <iostream> | |
| #include <cassert> | |
| using namespace std; | |
| typedef long long input_type; | |
| typedef vector<input_type> container; | |
| typedef deque<container> queue; | |
| container merge(const container& c1, const container& c2) | |
| { | |
| input_type c1_size = c1.size(); | |
| input_type c2_size = c2.size(); | |
| container c(c1_size + c2_size); | |
| input_type i = 0, j = 0; | |
| while (true) { | |
| if (i + j >= c.size()) { | |
| break; | |
| } | |
| if (i == c1_size) { | |
| c[i + j] = c2[j]; | |
| ++j; | |
| continue; | |
| } | |
| if (j == c2_size) { | |
| c[i + j] = c1[i]; | |
| ++i; | |
| continue; | |
| } | |
| if (c1[i] < c2[j]) { | |
| c[i + j] = c1[i]; | |
| ++i; | |
| } | |
| else if (c1[i] == c2[j]) { | |
| c[i + j] = c1[i]; | |
| ++i; | |
| c[i + j] = c2[j]; | |
| ++j; | |
| } | |
| else { | |
| c[i + j] = c2[j]; | |
| ++j; | |
| } | |
| } | |
| return c; | |
| } | |
| void iterative_merge_sort(queue& q) | |
| { | |
| while (q.size() > 1) { | |
| container c = merge(*(q.begin() + 1), *(q.begin() + 0)); | |
| q.pop_front(); | |
| q.pop_front(); | |
| q.push_back(c); | |
| } | |
| } | |
| container merge_sort(const container& c) | |
| { | |
| queue q; | |
| for (input_type i = 0; i < c.size(); ++i) { | |
| q.push_back(container(1, c[i])); | |
| } | |
| iterative_merge_sort(q); | |
| return q[0]; | |
| } | |
| input_type binary_search(const container& c, input_type begin, input_type end, input_type el) | |
| { | |
| input_type m = begin + (end - begin) / 2; | |
| if (c[m] == el) { | |
| while (m > 0 && c[m-1] == el) { | |
| --m; | |
| } | |
| return m; | |
| } | |
| else if (el <= c[m]) { | |
| return binary_search(c, begin, m, el); | |
| } | |
| else { | |
| return binary_search(c, m + 1, end, el); | |
| } | |
| } | |
| input_type find_inversion_coef(const container& c) | |
| { | |
| container sorted = merge_sort(c); | |
| input_type coef = 0, size = sorted.size(); | |
| for (size_t i = 0; i < c.size(); ++i) { | |
| input_type el = c[i]; | |
| input_type index = binary_search(sorted, 0, size, el); | |
| coef += index; | |
| sorted.erase(sorted.begin() + index); | |
| --size; | |
| } | |
| return coef; | |
| } | |
| int main() | |
| { | |
| // { | |
| // container c; | |
| // c.push_back(2); | |
| // c.push_back(3); | |
| // c.push_back(9); | |
| // c.push_back(2); | |
| // assert(find_inversion_coef(c) == 2); | |
| // c.push_back(9); | |
| // assert(find_inversion_coef(c) == 2); | |
| // } | |
| // { | |
| // container c(1,2); | |
| // assert(find_inversion_coef(c) == 0); | |
| // } | |
| // { | |
| // container c(5, 10000); | |
| // c[1] = 90; | |
| // c[2] = 90; | |
| // assert(find_inversion_coef(c) == 2); | |
| // } | |
| // { | |
| // container c(3); | |
| // c[0] = 10; | |
| // c[1] = 9; | |
| // c[2] = 8; | |
| // assert(find_inversion_coef(c) == 3); | |
| // } | |
| // { | |
| // container c(4); | |
| // for (size_t i = 0; i < c.size(); ++i) { | |
| // c[i] = 12-i; | |
| // } | |
| //// c[1] = 100; | |
| //// c[3] = 23; | |
| // assert(find_inversion_coef(c) == 6); | |
| // } | |
| // return 0; | |
| input_type n; | |
| cin >> n; | |
| container in(n); | |
| for (input_type i = 0; i < n; ++i) { | |
| input_type value; | |
| if (cin >> value) { | |
| in.push_back(value); | |
| } | |
| else { | |
| return 1; | |
| } | |
| } | |
| cout << find_inversion_coef(in); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment