Pagini recente » Cod sursa (job #1053443) | Cod sursa (job #2443603) | Cod sursa (job #222109) | Cod sursa (job #2472135) | Cod sursa (job #51055)
Cod sursa(job #51055)
#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 1030
int C, L, a[MAX];
int wool, m[MAX*MAX], m2[MAX*MAX];
int n, pivot, aux, pivot2;
int found, pos, rez;
vector<int> o;
set<vector<int> > mm;
FILE *fout = fopen("oite.out", "w");
void quickSort(int st, int dr);
int main()
{
o.resize(4);
FILE *fin = fopen("oite.in", "r");
fscanf(fin, "%d%d", &C, &L);
for (int i = 1; i <= C; ++i)
fscanf(fin, "%d", &a[i]);
fclose(fin);
for (int i = 1; i <= C; ++i)
for (int j = i+1; j <= C; ++j)
{
wool = a[i] + a[j];
m[n] = wool;
m2[n] = i*1030 + j;
n++;
}
int st, dr, mijl;
quickSort(0, n-1);
for (int i = 0; i < n; ++i)
{
if (m[i] > L / 2) break;
st = i;
dr = n-1;
found = 0;
while (st <= dr)
{
mijl = (st + dr) >> 1;
if (m[mijl] == (L - m[i]))
{
found = mijl;
break;
}
else
if (m[mijl] < (L - m[i]))
st = mijl + 1;
else
dr = mijl - 1;
}
if (found)
{
pos = found;
while (m[pos] == L - m[i])
{
o[0] = m2[i] / 1030;
o[1] = m2[i] % 1030;
o[2] = m2[pos] / 1030;
o[3] = m2[pos] % 1030;
sort(o.begin(), o.end());
if (!(o[0] == o[1] || o[0] == o[2] || o[0] == o[3] || o[1] == o[2] || o[1] == o[3] || o[2] == o[3]))
{
if (!mm.count(o))
{
mm.insert(o);
rez++;
}
}
pos++;
if (pos >= n) break;
}
pos = found-1;
while (m[pos] == L - m[i])
{
o[0] = m2[i] / 1030;
o[1] = m2[i] % 1030;
o[2] = m2[pos] / 1030;
o[3] = m2[pos] % 1030;
sort(o.begin(), o.end());
if (!(o[0] == o[1] || o[0] == o[2] || o[0] == o[3] || o[1] == o[2] || o[1] == o[3] || o[2] == o[3]))
{
if (!mm.count(o))
{
mm.insert(o);
rez++;
}
}
pos--;
if (pos < 0) break;
}
}
}
fprintf(fout, "%d\n", rez);
fclose(fout);
return 0;
}
void quickSort(int st, int dr)
{
int i = st - 1, j = dr + 1;
pivot = m[st];
do
{
do { i++; } while ((pivot > m[i]));
do { j--; } while ((pivot < m[j]));
if (i <= j)
{
aux = m[i];
m[i] = m[j];
m[j] = aux;
aux = m2[i];
m2[i] = m2[j];
m2[j] = aux;
}
} while (i <= j);
if (i < dr) quickSort(i, dr);
if (j > st) quickSort(st, j);
}