Pagini recente » Cod sursa (job #464845) | Cod sursa (job #1058091) | Cod sursa (job #1098128) | Istoria paginii runda/ichc_preoji2010/clasament | Cod sursa (job #76045)
Cod sursa(job #76045)
#include <cstdio>
#include <vector>
using namespace std;
#define maxn 1024
#define maxp 204729
#define maxp2 154729
FILE *in = fopen("oite.in", "r"), *out = fopen("oite.out", "w");
struct hash
{
short i, j;
};
int n;
int L;
int a[maxn];
vector<hash> h[maxp];
int nr[maxp];
vector<hash> h2[maxp2];
int nr2[maxp2];
void hadd(int p, int q)
{
int t = (a[p] + a[q]) % maxp;
int d = (a[p] + a[q]) % maxp2;
hash tt;
tt.i = p;
tt.j = q;
if ( nr[t] < nr2[d] )
h[t].push_back(tt), ++nr[t];
else
h2[t].push_back(tt), ++nr2[d];
}
int hget(int p, int q)
{
if ( L - (a[p] + a[q]) < 0 )
return 0;
int s = 0;
int v = (L - (a[p] + a[q]));
int t = v % maxp;
int d = v % maxp2;
int i;
if ( nr[t] < nr2[t] )
{
for ( i = 0; i != nr[t]; ++i )
{
if ( h[t][i].i > q && a[h[t][i].i] + a[h[t][i].j] == v )
++s;
if ( h2[d][i].i > q && a[h2[d][i].i] + a[h2[d][i].j] == v )
++s;
}
for ( ; i != nr2[t]; ++i )
if ( h2[d][i].i > q && a[h2[d][i].i] + a[h2[d][i].j] == v )
++s;
}
else
{
for ( i = 0; i != nr2[d]; ++i )
{
if ( h2[d][i].i > q && a[h2[d][i].i] + a[h2[d][i].j] == v )
++s;
if ( h[t][i].i > q && a[h[t][i].i] + a[h[t][i].j] == v )
++s;
}
for ( ; i != nr[t]; ++i )
if ( h[t][i].i > q && a[h[t][i].i] + a[h[t][i].j] == v )
++s;
}
return s;
}
int main()
{
fscanf(in, "%d %d", &n, &L);
for ( int i = 0; i < n; ++i )
fscanf(in, "%d", &a[i]);
for ( int i = 0; i < n; ++i )
for ( int j = i+1; j < n; ++j )
hadd(i, j);
int cnt = 0;
for ( int i = 0; i < n; ++i )
for ( int j = i+1; j < n; ++j )
cnt += hget(i, j);
fprintf(out, "%d\n", cnt);
return 0;
}