Cod sursa(job #2716679)

Utilizator PredescuSebastianIonPredescu Sebastian Ion PredescuSebastianIon Data 5 martie 2021 15:05:02
Problema Dtcsu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("dtcsu.in");
ofstream g("dtcsu.out");
const int mod=10007;
long long cate=0,x,q;
vector <long long> v[mod];
int main()
{
    for(long long i=1; i<=276997; i++)
    {
        f>>x;
        v[x%mod].push_back(x);
    }
    for(long long i=0; i<mod; i++)
    {
        sort(v[i].begin(),v[i].end());
    }
    f>>q;
    while(q--)
    {
        f>>x;
        long long rest=x%mod;
        if(v[rest].empty())continue;
        if(x<v[rest][0])continue;
        long long mij,p,u;
        p=0;
        u=v[rest].size()-1;
        while (p<u)
        {
            mij=(p+u)/2;
            if(v[rest][mij]>x)
            {
                u=mij-1;
            }
            else if(v[rest][mij]<x)
            {
                p=mij+1;
            }
            else p=u=mij;
        }
        if(v[rest][u]==x)cate++;
    }
    g<<cate<<'\n';
    return 0;
}