summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Sources/DataStructure.cpp217
1 files changed, 97 insertions, 120 deletions
diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp
index e76d5be..f3d46be 100644
--- a/Sources/DataStructure.cpp
+++ b/Sources/DataStructure.cpp
@@ -1,141 +1,118 @@
#include <iostream>
-#include <queue>
#include <vector>
+#include <algorithm>
//#include <gtest/gtest.h>
-struct Request {
- Request(int arrival_time, int process_time) :
- arrival_time(arrival_time), process_time(process_time) {
- }
+using std::vector;
+using std::cin;
+using std::cout;
+using std::swap;
+using std::pair;
+using std::make_pair;
- int arrival_time;
- int process_time;
-};
+class HeapBuilder {
+private:
+ vector<int> data_;
+// vector<pair<int, int> > 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));
+// }
+// }
+// }
-struct Response {
- Response(bool dropped, int start_time) :
- dropped(dropped), start_time(start_time) {
+public:
+ vector<pair<int, int>> 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";
+ }
}
- bool dropped;
- int start_time;
-};
-
-class Buffer {
-public:
- Buffer(int capacity) :
- capacity_(capacity), finish_time_() {
+ void ReadData() {
+ int n;
+ cin >> n;
+ data_.resize(n);
+ for (int i = 0; i < n; ++i)
+ cin >> data_[i];
}
- Response Process(const Request &request) {
- // write your code here
- if (runningTimeCounter_ < request.arrival_time) {
- if (finish_time_.size() == 0)
- runningTimeCounter_ = request.arrival_time;
- else if (finish_time_.back() < request.arrival_time)
- runningTimeCounter_ = request.arrival_time;
+ // 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<int> &data) {
+ int j = (data.size() - 1) / 2;
+ while (j >= 0) {
+ siftDown(j, data);
+ j = j - 1;
}
- while (finish_time_.size() > 0) {
- int j = finish_time_.front();
- if (j <= request.arrival_time)
- finish_time_.pop();
- else
- break;
- }
-
- if (finish_time_.size() >= capacity_) {
- return Response(true, -1);
+// for (size_t i = j; i >= 0; i--) {
+// siftDown(i, data);
+// }
+ }
+ void siftDown(int i, vector<int> &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);
}
- Response response = Response(false, runningTimeCounter_);
- runningTimeCounter_ = runningTimeCounter_ + request.process_time;
- if (finish_time_.size() > 0)
- finish_time_.push(finish_time_.back() + request.process_time);
- else
- finish_time_.push(runningTimeCounter_);
- return response;
-
}
-private:
- size_t capacity_;
- std::queue<int> finish_time_;
- int runningTimeCounter_ = 0;
-};
-
-std::vector<Request> ReadRequests() {
- std::vector<Request> requests;
- int count;
- std::cin >> count;
- for (int i = 0; i < count; ++i) {
- int arrival_time, process_time;
- std::cin >> arrival_time >> process_time;
- requests.push_back(Request(arrival_time, process_time));
+ void Solve() {
+ ReadData();
+// GenerateSwaps();
+ UpdateSwaps(data_);
+ WriteResponse();
}
- return requests;
-}
-
-std::vector<Response> ProcessRequests(const std::vector<Request> &requests,
- Buffer *buffer) {
- std::vector<Response> responses;
- for (size_t i = 0; i < requests.size(); ++i)
- responses.push_back(buffer->Process(requests[i]));
- return responses;
-}
+};
-void PrintResponses(const std::vector<Response> &responses) {
- for (size_t i = 0; i < responses.size(); ++i)
- std::cout << (responses[i].dropped ? -1 : responses[i].start_time)
- << std::endl;
+int main() {
+// vector<int> 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(ProcessRequests, t) {
-// int bufferMaxSize = 1;
-// Buffer buf = Buffer(bufferMaxSize);
-// std::vector<Request> requests;
-// std::vector<Response> responses = ProcessRequests(requests, &buf);
-// ASSERT_EQ(0, responses.size());
-//}
-//
-//TEST(ProcessRequests, t1) {
-// int bufferMaxSize = 1;
-// Buffer buf = Buffer(bufferMaxSize);
-// std::vector<Request> requests = {Request(0, 1)};
-// std::vector<Response> responses = ProcessRequests(requests, &buf);
-// ASSERT_EQ(1, responses.size());
-// ASSERT_EQ(false, responses[0].dropped);
+//TEST(BuildHeap, t) {
+// vector<int> 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(ProcessRequests, t2) {
-// int bufferMaxSize = 1;
-// Buffer buf = Buffer(bufferMaxSize);
-// std::vector<Request> requests = {Request(0, 1), Request(0, 1)};
-// std::vector<Response> responses = ProcessRequests(requests, &buf);
-// ASSERT_EQ(2, responses.size());
-// ASSERT_EQ(false, responses[0].dropped);
-// ASSERT_EQ(0, responses[0].start_time);
-// ASSERT_EQ(true, responses[1].dropped);
+//TEST(BuildHeap, t1) {
+// vector<int> data = {1, 2, 3, 4, 5};
+// HeapBuilder heap_builder;
+// heap_builder.UpdateSwaps(data);
+// ASSERT_EQ(0, heap_builder.swaps.size());
//}
//
-//TEST(ProcessRequests, t3) {
-// int bufferMaxSize = 1;
-// Buffer buf = Buffer(bufferMaxSize);
-// std::vector<Request> requests = {Request(0, 1), Request(1, 1)};
-// std::vector<Response> responses = ProcessRequests(requests, &buf);
-// ASSERT_EQ(2, responses.size());
-// ASSERT_EQ(false, responses[0].dropped);
-// ASSERT_EQ(0, responses[0].start_time);
-// ASSERT_EQ(false, responses[1].dropped);
-// ASSERT_EQ(1, responses[1].start_time);
-//}
-
-int main() {
- int size;
- std::cin >> size;
- std::vector<Request> requests = ReadRequests();
-
- Buffer buffer(size);
- std::vector<Response> responses = ProcessRequests(requests, &buffer);
-
- PrintResponses(responses);
- return 0;
-}
-
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 13:18:28 +0000