Elo , próbuje optymalnie uporać się z zadaniem "Fish" z Codility.com , ale z niewiadomych mi przyczyn kolejka , którą czyszczę funkcją ClearQueue() nadal posiada elementy i z każdą iteracją śmieci jest coraz więcej. Rozwiązanie czyszczenia pętlą do while nie wchodzi w grę bo stracę wtedy złożoność O(n). Może mi , ktoś wyjaśnić gdzie popełniam błąd?
Dokładną instrukcję do zadania można obejrzeć tutaj : https://codility.com/programmers/lessons/5
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include <queue>
using namespace std;
void ClearQueue(queue<int> &CollisionQueue)
{
cout<<CollisionQueue.size();
for(int i=0;i<CollisionQueue.size();i++)
{
CollisionQueue.pop();
}
cout<<" "<<CollisionQueue.size()<<endl;
}
void Elimination(int DownstreamSwimmerId,vector<int> &A, vector<int> &B,queue<int> &CollisionQueue)
{
unsigned int ColQuePrevSize=CollisionQueue.size(),DeadCount=0;
for(unsigned int i=0;i<ColQuePrevSize;i++)
{
if(A[DownstreamSwimmerId]>A[CollisionQueue.front()-DeadCount])
{
//cout<<"0";
A.erase(A.begin()+CollisionQueue.front()-DeadCount);
B.erase(B.begin()+CollisionQueue.front()-DeadCount);
CollisionQueue.pop();
DeadCount++;
}
else
{
if(A[DownstreamSwimmerId]<A[CollisionQueue.front()-DeadCount])
{
A.erase(A.begin()+DownstreamSwimmerId);
B.erase(B.begin()+DownstreamSwimmerId);
break;
}
}
}
}
int solution(vector<int> &A, vector<int> &B) {
queue<int>CollisionQueue;
for(int i=A.size()-2;i>-1;i--)
{
if(B[i])
{
for(unsigned int j=i+1;j<A.size();j++)
{
if(!B[j])
{
CollisionQueue.push(j);
}
}
Elimination(i,A,B,CollisionQueue);
ClearQueue(CollisionQueue);
}
}
return A.size();
}
Input:
100000 pseudolosowych wielkości ryb i 100000 losowych kierunków {0,1}.
Output:
1 0
1 0
1 0
1 0
3 1
4 2
4 2
6 3
10 5
10 5
11 5
12 6
10 5
RUNTIME ERROR (tested program terminated unexpectedly)