Program freezing if function is present after the freezing point-CodePudding

When function analiza() isn't commented, my program shows both messages in input() function. (przed, po), But, if I uncomment the analiza() after input(), it breaks. I tried cleaning buffers, diffrent libraries ect. NOTHING helped. Code:

#include <iostream>
using namespace std;

unsigned int liczba_osob, liczba_klapek, przeszli = 0;
unsigned long long osoby[200000], klapki[200000], minimum;
bool do_uzycia[200000]{0};

unsigned long long greatest();
bool czy_mozliwe(unsigned int osoba);
void input();
void analiza();

int main()
{
    input();
  analiza();
    return 0;
}

unsigned long long greatest()
{
    unsigned long long maxrn = klapki[0];
    for (unsigned int i = 1; i < liczba_klapek; i  )
        if (klapki[i] > maxrn)
            maxrn = klapki[i];
    return maxrn;
}

bool czy_mozliwe(unsigned int osoba)
{
    if (osoby[osoba] >= minimum)
        return 1;
    unsigned long long maximim = greatest();
    if (osoby[osoba]   maximim < minimum)
        return 0;
    for (unsigned int i = 0; i < liczba_klapek; i  )
    {
        if (osoby[osoba]   klapki[i] >= minimum && !do_uzycia[i])
        {
            do_uzycia[i] = 1;
            return 1;
        }
    }
    return 0;
}
void input()
{
    cin >> liczba_osob;
    for (unsigned int i = 0; i < liczba_osob; i  )
        cin >> osoby[i];

    cin >> liczba_klapek;
    for (unsigned int i = 0; i < liczba_klapek; i  )
        cin >> klapki[i];
cout<<"przed";
    cin >> minimum;
    cout<<"po";
}
void analiza()
{
     for (unsigned int i = 0; i < liczba_osob; i  )
        if (czy_mozliwe(i))
            przeszli  ;
    cout << przeszli;
}

So, the problem rn is with input:

200000
10 20 30... (and 199997 times more)
200000
10 20 30... (and 199997 more)
2500000

so max input due to arrays being 200000 long. Program freezes in the input() after cout<<"przed";. It doesn't get input to the minimum variable. If I remove call to analiza() in int main(), the problem doesn't occurr.

Here's the input file that makes the problem file

CodePudding user response：

For the given input, your function analiza makes 200000 = 2 * 10^5 calls to the function czy_mozliwe. That function in turn calls greatest, which makes 2 * 10^5 iterations of a loop with a comparison in each iteration, and then czy_mozliwe proceeds to run its own loop with 2 * 10^5 iterations.

So in order to finish executing analiza, the computer needs to execute 4 * 10^10 iterations of the loop in greatest and 4 * 10^10 iterations of the loop in czy_mozliwe.

That might take a long time.

Meanwhile the output you queued up with cout<<"po"; may just be waiting in a buffer. You haven't seen it come out because you didn't flush the buffer when you wrote it. Try cout<<"po"<<std::endl; instead.

Then you might think about how you can write your program so it doesn't require so many iterations of its inner loops.