Cod sursa(job #2622325)

Utilizator ihorvaldsTudor Croitoru ihorvalds Data 31 mai 2020 22:28:13
Problema Statistici de ordine Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

void merge_arrays(std::vector<int>& v, int start, int mid, int end) {

    std::vector<int> copy;
    int size = end - start + 1;

    int i = 0, j = 0;
    while ((start + i) <= mid && (mid + 1 + j) <= end) {
        if (v[start + i] <= v[mid + 1 + j]) {
            copy.push_back(v[start + i]);
            i++;
        } else {
            copy.push_back(v[mid + 1 + j]);
            j++;
        }
    }

    if (start + i == mid + 1) {
        // mid +1 + j -> end
        for (int k = mid + 1 + j; k <= end; k++) {
            copy.push_back(v[k]);
            j++;
        }
    } 
    
    if (mid + 1 + j == end + 1) {
        for (int k = start + i; k <= mid; k++) {
            copy.push_back(v[k]);
            i++;
        }
    }

    // copying the copy in the array

    for (int l = 0; l < size; l++) {
        v[start + l] = copy[l];
    }
}

void merge_sort(std::vector<int>& v, int low, int high) {
    if (high == low) {
        return;
    }

    int mid = (low + high) / 2;
    merge_sort(v, low, mid);
    merge_sort(v, mid + 1, high);
    merge_arrays(v, low, mid, high);
}

int main() {
    std::ifstream f("sdo.in");
    std::ofstream g("sdo.out");

    int n, i;
    f >> n >> i;

    //std::vector<int> a;
    int* a = new int[i] {0};
    int j = 0;
    int tmp;
    for (j = 0; j < i; j++) {
        f >> tmp;
        a[j] = tmp;
    }

    std::sort(a, a + i);
    while (!f.eof()) {
        //merge_sort(a, 0, i);
        f >> tmp;
        if (tmp < a[i-1]) {
            a[i-1] = tmp;
        }
    }

    std::cout << a[i-1] << "\n";
}