fork(1) download
copy 
  1. #include <mpi.h>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <iostream>
  5.  
  6. void longest_increasing_subsequence(std::vector<int>& arr, int n, int& length, int& last_element) {
  7.     length = 1;
  8.     last_element = arr[0];
  9.  
  10.     for (int i = 1; i < n; i++) {
  11.         if (arr[i] < last_element) {
  12.             continue;
  13.         } else if (arr[i] == last_element) {
  14.             length++;
  15.         } else {
  16.             last_element = arr[i];
  17.             length = std::max(length, static_cast<int>(i) + 1);
  18.         }
  19.     }
  20. }
  21.  
  22. int main(int argc, char *argv[]) {
  23.     MPI_Init(&argc, &argv);
  24.  
  25.     int rank, size;
  26.     MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  27.     MPI_Comm_size(MPI_COMM_WORLD, &size);
  28.  
  29.     if (argc != 2) {
  30.         if (rank == 0) {
  31.             std::cerr << "Usage: " << argv[0] << " <input_file>" << std::endl;
  32.         }
  33.         MPI_Finalize();
  34.         return 1;
  35.     }
  36.  
  37.     std::vector<int> arr;
  38.     int n, length, last_element;
  39.  
  40.     if (rank == 0) {
  41.         // Read input from file
  42.         // ...
  43.     }
  44.  
  45.     // Broadcast input size and array to all processes
  46.     MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
  47.     MPI_Bcast(&arr[0], n, MPI_INT, 0, MPI_COMM_WORLD);
  48.  
  49.     // Calculate longest increasing subsequence on each process
  50.     int start = (n / size) * rank;
  51.     int end = start + (n / size);
  52.     if (rank == size - 1) {
  53.         end = n;
  54.     }
  55.  
  56.     int local_length = 0, local_last_element = 0;
  57.     longest_increasing_subsequence(std::vector<int>(arr.begin() + start, arr.begin() + end), end - start, local_length, local_last_element);
  58.  
  59.     // Gather all lengths and find the maximum
  60.     std::vector<int> lengths(size);
  61.     MPI_Gather(&local_length, 1, MPI_INT, &lengths[0], 1, MPI_INT, 0, MPI_COMM_WORLD);
  62.  
  63.     if (rank == 0) {
  64.         length = *std::max_element(lengths.begin(), lengths.end());
  65.         std::cout << "Length of longest increasing subsequence: " << length << std::endl;
  66.     }
  67.  
  68.     MPI_Finalize();
  69.     return 0;
  70. }
Success #stdin #stdout #stderr 0.27s 40864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Error: unexpected symbol in "void longest_increasing_subsequence"
Execution halted
https://ideone.com/SCWFUJ
language:
R (R 3.5.2)
created:
2 years 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!