Cod sursa(job #2636852)

Utilizator loraclorac lorac lorac Data 20 iulie 2020 14:25:23
Problema Dtcsu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("dtcsu.in");
ofstream out("dtcsu.out");
typedef long long ll;
const ll mod=10007;
vector<ll> h[mod+3];
int main()
{
    ll n=276997,tst,x;
    for(ll i=1;i<=n;++i)
    {
        in>>x;
        h[x%mod].push_back(x);
    }
    for(ll i=0;i<mod;++i)
        sort(h[i].begin(),h[i].end());
    in>>tst;
    ll ans=0;
    while(tst--)
    {
        in>>x;
        ll cat=x%mod;
        if(x<h[cat][0]) continue;
        ll l=0,r=h[cat].size()-1,med;
        while(l<r)
        {
            if(r==l+1)
                med=r;
            else med=(l+r)/2;
            if(h[cat][med]<x) l=med;
            else if(h[cat][med]>x) r=med-1;
            else l=r=med;
        }
        if(h[cat][l]==x) ++ans;
    }
    out<<ans<<'\n';
    return 0;
}