Cod sursa(job #2556728)

Utilizator NegreaVlad00Negrea Vlad Andrei NegreaVlad00 Data 25 februarie 2020 10:13:03
Problema Sortare prin comparare Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
using namespace std;
 ifstream f("algsort.in");
 ofstream g("algsort.out");
int a[500005],b[5000005];

void interclasare(int st, int mij, int dr)
{
    int i,j,k,t;
    for(i=st;i<=dr;i++) b[i]=a[i];
    i=st;
    j=mij+1;
    k=st-1;
    while(i<=mij&&j<=dr)
        if(b[i]<b[j]) a[++k]=b[i++];
        else a[++k]=b[j++];
    for(t=i;t<=mij;t++) a[++k]=b[t];
    for(t=j;t<=dr;t++) a[++k]=b[t];
}

void sortare(int st, int dr)
{
    int mij;
    if(st!=dr)
    {
        mij=(st+dr)/2;
        sortare(st,mij);
        sortare(mij+1,dr);
        interclasare(st,mij,dr);
    }
}

int main()
{int i,n,m,j,nr=0,dr,st,mij,poz;
    f>>n>>m;
    for(i=1;i<=n;i++) f>>a[i];
    sortare(1,n);
    for(i=1;i<=n&&a[i]<=n/2;i++)
    {
        st=1;
        dr=n;
        poz=0;
        while(st<=dr&&poz==0)
        {
            mij=(st+dr)/2;
            if((a[mij]+a[i])==m)
            {
                poz++;
                nr++;
            }
            else
                if((a[mij]+a[i])>m) dr=mij-1;
                else st=mij+1;
        }
    }
    cout<<nr;

    return 0;
}