Cod sursa(job #1790937)

Utilizator tanasaradutanasaradu tanasaradu Data 28 octombrie 2016 21:29:56
Problema Interclasari Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("interclasari.in");
ofstream fout("interclasari.out");
int n,m,a[20000001];
void Inserare(int &n,int poz,int val)
{
    int i;
    for(i=n;i>=poz;i--)
        a[i+1]=a[i];
    n++;
    a[poz]=val;
}
int CautBin(int x)
{
    int st=1,dr=n,mij,poz=-1;
    if(a[1]>=x)return 1;
    if(a[n]<=x)return n;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]==x)
            return mij;
        if(a[mij]<x)
        {
            poz=mij;
            st=mij+1;
        }
        else dr=mij-1;
    }
    return poz;
}
int main()
{
    int i,j,k,val,x;
    fin>>m;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    for(i=1;i<m;i++)
    {
        fin>>k;
        for(j=1;j<=k;j++)
        {
            fin>>val;
            x=CautBin(val);
            Inserare(n,x+1,val);
        }
    }
    fout<<n<<"\n";
    for(i=1;i<=n;i++)
        fout<<a[i]<<" ";
    fin.close();
    fout.close();
    return 0;
}