#include #include #include //#include using std::vector; using std::cin; using std::cout; using std::swap; using std::pair; using std::make_pair; class HeapBuilder { private: vector data_; // vector > swaps_; // void GenerateSwaps() { // swaps_.clear(); // // The following naive implementation just sorts // // the given sequence using selection sort algorithm // // and saves the resulting sequence of swaps. // // This turns the given array into a heap, // // but in the worst case gives a quadratic number of swaps. // // // for (size_t i = 0; i < data_.size(); ++i) // for (size_t j = i + 1; j < data_.size(); ++j) { // if (data_[i] > data_[j]) { // swap(data_[i], data_[j]); // swaps_.push_back(make_pair(i, j)); // } // } // } public: vector> swaps; void WriteResponse() const { cout << swaps.size() << "\n"; for (size_t i = 0; i < swaps.size(); ++i) { cout << swaps[i].first << " " << swaps[i].second << "\n"; } } void ReadData() { int n; cin >> n; data_.resize(n); for (int i = 0; i < n; ++i) cin >> data_[i]; } // Please note the for loop below. Initially I copied the for loop from my // Java code, but it doesn't work in C++. Changing it to while loop worked! // It was better with the while loop anyway, much clearer to me. void UpdateSwaps(vector &data) { int j = (data.size() - 1) / 2; while (j >= 0) { siftDown(j, data); j = j - 1; } // for (size_t i = j; i >= 0; i--) { // siftDown(i, data); // } } void siftDown(int i, vector &data) { int maxIndex = i; size_t l = 2 * i + 1; if (l < data.size() && data[l] < data[maxIndex]) maxIndex = l; size_t r = 2 * i + 2; if (r < data.size() && data[r] < data[maxIndex]) maxIndex = r; if (i != maxIndex) { swap(data[i], data[maxIndex]); swaps.push_back(make_pair(i, maxIndex)); siftDown(maxIndex, data); } } void Solve() { ReadData(); // GenerateSwaps(); UpdateSwaps(data_); WriteResponse(); } }; int main() { // vector data = { 5, 4, 3, 2, 1 }; // HeapBuilder heap_builder; // heap_builder.UpdateSwaps(data); // heap_builder.WriteResponse(); std::ios_base::sync_with_stdio(false); HeapBuilder heap_builder; heap_builder.Solve(); return 0; } //TEST(BuildHeap, t) { // vector data = {5, 4, 3, 2, 1}; // HeapBuilder heap_builder; // heap_builder.UpdateSwaps(data); // ASSERT_EQ(3, heap_builder.swaps.size()); // ASSERT_EQ(1, heap_builder.swaps[0].first); // ASSERT_EQ(4, heap_builder.swaps[0].second); // ASSERT_EQ(0, heap_builder.swaps[1].first); // ASSERT_EQ(1, heap_builder.swaps[1].second); // ASSERT_EQ(1, heap_builder.swaps[2].first); // ASSERT_EQ(3, heap_builder.swaps[2].second); //} // //TEST(BuildHeap, t1) { // vector data = {1, 2, 3, 4, 5}; // HeapBuilder heap_builder; // heap_builder.UpdateSwaps(data); // ASSERT_EQ(0, heap_builder.swaps.size()); //} //