Question

Cum se face problema nebuni de pe campion.edu.ro, daca iau matrice de un milion cu bool imi zice in codeblocks: "size of v is too large". Vreau doar o idee, nu rezolvarea problemei, multumesc anticipat. Deci intrebarea mea este cum pot sa retin pozitiile de atac ale nebuniilor ca sa-mi dea buil and run ? sau mai bine zise pot sa retin aceste pozitii ? Din nou nu vreau toata rezolvarea problemei.

nebuni


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
25MB / 1MB

Pe o tablă de şah cu N linii şi N coloane sunt plasaţi M nebuni. După cum se ştie de la jocul de şah, nebunii atacă doar în diagonală.
O poziţie de pe tabla de şah este considerată sigură dacă nu este atacată de niciun nebun aflat pe tablă.
Cerinţă

Scrieţi un program care să determine numărul de poziţii sigure de pe tabla de şah.
Date de intrare

Fişierul de intrare nebuni.in conţine pe prima linie numerele naturale N M, separate prin spaţiu, cu semnificaţia din enunţ. Pe următoarele M linii sunt descrise poziţiile (linia şi coloana, separate prin spaţiu) celor M nebuni, câte un nebun pe o linie a fişierului.
Date de ieşire

Fişierul de ieşire nebuni.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul de poziţii sigure de pe tabla de şah.
Restricţii

• 1 ≤ N ≤ 1 000 000
• 1 ≤ M < 16 500
• Liniile şi coloanele sunt numerotate de la 1 la N.
• Pentru 50% dintre teste N ≤ 300.
• Pentru 60% dintre teste M ≤ 1000.

nebuni.in nebuni.out Explicaţii
5 4 6 Pe tabla de şah de dimensiune 5x5 se află 4 nebuni.
2 1 Poziţiile atacate de cei 4 nebuni sunt marcate cu gri.
1 3
4 2
5 2

Answer 1

Te pot ajuta cu solutia oficiala - restul ... te descurci prin analiza pas cu pas. Succes!
#include <fstream>
#define NMAX 1000001
#define MMAX 100001

using namespace std;

int N, M;
int X[MMAX], Y[MMAX];
int DP[2*NMAX], DS[2*NMAX];
int nrs[2*NMAX];
long long int Rez;

void citire();
void afisare();
void rezolvare();

int main()
{
citire();
rezolvare();
afisare();
return 0;
}


void afisare()
{ofstream fout("nebuni.out");
 fout<<Rez<<'\n';
 fout.close();
}

void citire()
{ifstream fin("nebuni.in");
 int i;
 fin >> N >> M;
 for (i=1; i<=M; i++)
     fin>>X[i]>>Y[i];
}
 
int nrcelule(int i)
{
if (i <= N) return i;
return 2*N-i;
}


void rezolvare()
{int i, Sf, Inc, LInceput, CInceput, LSfarsit, CSfarsit, SI, SDS, SDP;
for (i=1; i<=M; i++)
    {DP[X[i] - Y[i] + N]=1;
     DS[X[i] + Y[i] - 1]=1;};
SDP=SDS=0;
for (i=1; i<2*N; i++)
    {if (DP[i]) SDP+=nrcelule(i);
     if (DS[i]) SDS+=nrcelule(i);}

nrs[1]=DS[1]==1;
for (i=2; i<2*N; i++) nrs[i]=nrs[i-2]+(DS[i]==1);

SI=0;  
for (i=1; i<2*N; i++)
if (DP[i]) 
{if (i<=N) {LInceput=1; CInceput = N-i+1; LSfarsit=i; CSfarsit=N;}
    else {LInceput=i-N+1; CInceput = 1; LSfarsit=N; CSfarsit =2*N-i;}
    Sf=LSfarsit+CSfarsit-1;
    Inc=LInceput+CInceput-1;
SI+=nrs[Sf]-nrs[Inc-2];
}

Rez=(long long int)N*N - (SDP+SDS-SI);
}