Cod sursa(job #2634600)

Utilizator betybety bety bety Data 11 iulie 2020 16:38:57
Problema Dtcsu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;
	char read_ch() {
		++sp;
		if (sp == 4096)
        {sp = 0; fread(buff, 1, 4096, fin);}
		return buff[sp];
	}
public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	InParser& operator >> (ll &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		ll sgn = 1;
		if (c == '-')
        {n = 0; sgn = -1;}
		else n = c - '0';
		while (isdigit(c = read_ch()))
			n = 10 * n + c - '0';
		n *= sgn;
		return *this;
	}
};
InParser in("dtcsu.in");
ofstream out("dtcsu.out");
ll n=276997,mod=10007;
vector<ll> v[10010];
int main()
{
    ll tst,x,ans=0;
    for(ll i=1;i<=n;++i) in>>x,v[x%mod].push_back(x);
    for(ll i=0;i<mod;++i) sort(v[i].begin(),v[i].end());
    in>>tst;
    while(tst--)
    {
        in>>x; if(!v[x%mod].size()) continue;
        int l=0,r=v[x%mod].size()-1,med;
        while(l<r)
        {
            med=(l+r)/2;
            if(v[x%mod][med]>x) r=med-1;
            else if(v[x%mod][med]<x) l=med+1;
            else l=r=med;
        }
        if(v[x%mod][l]==x) ++ans;
    }
    out<<ans<<'\n';
    return 0;
}