[problem solved, thx for answering]
I have a sorted vector v
and a vector num
, this is how I delete elements in vector v
:
vector <int> v;
vector <int> num;
//gets input
//for an example: v = {1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 6}
//num.size() = 0
num.push_back(v[v.size()-1]); //adds num "v"'s maximum element
v.erase(v.begin()+v.size()-1); // removes that element
while(v.size() > 0) {
num.push_back(v.back()); //adds num "v"'s maximum element
v.erase(v.begin()+v.size()-1); // removes that element
for(int i = 0; i < num.size()-1; i++) // checkes all elements of num except the last one added
{
int ggcd = __gcd(num[num.size()-1], num[i]);
int fnd = findv(v, ggcd); // finds GCD of maximum element and element i of num
v.erase(v.begin()+fnd); // removes
fnd = findv(v, ggcd); //repeats one more time
v.erase(v.begin()+fnd);
}
}
where function findv(vector<int> v, int x)
is a function that finds the index of smallest element that is not less than x
by binary search:
int findv(const vector<int>& v, int x) // simply, finds
{
int l = 0, r = sz(v), mid;
while(r-l > 1)
{
mid = (l+r)/2;
if(v[mid] < x) l = mid;
else if(v[mid] > x) r = mid;
else return mid;
}
return l;
}
size of vector v in the start is always square of some n (4 here) so the vector size never reaches 0 in middle of the while.
The runtime error is from the v.erase(v.begin()+fnd)
in the for
as when I delete them, there is no runtime error and the v.erase(v.begin()+v.size()-1)
s before the while/for work perfectly
after I found out the problem is about erasing in the for, I replaced them with v.erase(v.begin()+0)
to see if the problem is in function findv. but that also gave me a runtime error, I replaced it with many other numbers, size-1 and everything but still, there was a runtime error. I searched a lot in internet and even tried to change how I delete elements from v but they had other errors/didnt do what I want. for an example this:
v.erase(remove(v.begin(), v.end(), __gcd(num[sz(num)-1], num[i])), v.end());
deletes by value, but it deletes all elements of that value which isnt what I want. and tried this:
vector<int>::iterator it = find(v.begin(), v.end(), __gcd(num[sz(num)-1], num[i]));
int index = distance(v.begin(), it);
v.erase(v.begin()+index);
it = find(v.begin(), v.end(), __gcd(num[sz(num)-1], num[i]));
index = distance(v.begin(), it);
v.erase(v.begin()+index);
But this one also gave me a runtime error. the elements dont run out while in the while cause n^2 + 2*n + 1 = (n+1)^2 which is n^2 for another n. its provable by a mathematical induction. Btw, if u want to know what I am exactly doing in the code, its a solution for this problem: https://codeforces.com/problemset/problem/582/A and this is a full version of my code: https://ideone.com/suu0GG
I did not exactly find out what was actually wrong in my code but, seems like my problem was not about the erasing part and other things were wrong. I dont know why there was no runtime after removing the erase part, maybe it was a compiler error. these are things I changed to make it work:
also one user here asked me why did I use a hand made function 'findv' while lowerband and upperband exist and well that's a valid problem for my code. (I had reasons for it, but I am saying it generally)