0

Bellow, I attach my code, can someone tell me why do I get a runtime error?

For input 1 5 1 2 1 3 1 the correct answer is 2. This example works, but when I put this algorithm to the checker I get "Run time error"

#include <bits/stdc++.h>
using namespace std;

int main()
{
      int z;
      cin >> z;
      for (int ii = 0; ii < z; ii++)
      {
        int k;
        cin >> k;
        vector <int> p(k,0);
        for (int i = 0; i < k; i++)
        {
            int m;
            cin >> m;
            p[m]++;
        }
        sort(p.begin(),p.end());
        int sm = p[0] + p.size()-1;
              for (int i = 1; i < p.size(); i++)
              {
                      int cm = p[i] + p.size()-i-1;
                      if(cm<sm)sm = cm;
              }
              cout << sm << endl;

      }
}
  • 1
    Unrelated to your problem, but please take some time to read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) as well as [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). And generally don't use online judge/competition sites as a learning resource because they aren't. Take classes, read [books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) instead. – Some programmer dude Apr 10 '20 at 05:39
  • Can't see any obvious problem. Do you know what the 'checker' is doing? – john Apr 10 '20 at 05:40
  • I do not know what 'checker' is doing, it would be too easy if I know. I have to solve this because it is an exercise for my Universitet. –  Apr 10 '20 at 05:50
  • It `p` is empty, then you will get an out-of-bounds access: `int sm = p[0] + p.size()-1;` As a matter of fact, it is easy to come up with input that will blow this program up. – PaulMcKenzie Apr 10 '20 at 05:51
  • So what should I change? –  Apr 10 '20 at 05:54
  • You can't assume that `p` has elements, but your code does. Second `p[m]` -- what if `m` is some wild value, outside the bounds of `p`? Bottom line -- there is no data verification in your program, and we don't know if good data is guaranteed. Given the error, the only reason I see it not working is for erroneous data that you are not checking for. – PaulMcKenzie Apr 10 '20 at 05:55
  • 1)I fill the vector with zeroes, so I can assume that p has elements. 2) how can I do data validation? –  Apr 10 '20 at 05:59
  • You are incrementing p[m], what if the input is greater than vector size? Won't this cause runtime error? – Wander3r Apr 10 '20 at 06:00
  • `vector p(k,0);` -- If `k` is 0, that vector will have no elements. A simple input of `1 0` will cause issues. If you want proof, don't change anything in your code, and give it that input. In addition, you should use `at()` instead of `[ ]` to access the vector elements -- then instead of a runtime error, you may get a `std::out_of_bounds` exception thrown, proving that the vector is being accessed out of bounds. – PaulMcKenzie Apr 10 '20 at 06:00
  • The k value can be: 1≤k≤1000000 I have this information in the content of the task –  Apr 10 '20 at 06:09
  • If the input is `1 1 1` I get: `terminate called after throwing an instance of 'std::out_of_range' what(): vector::_M_range_check: __n (which is 1) >= this->size() (which is 1)` How can I fix this? –  Apr 10 '20 at 06:10
  • Maybe set the size of the vector to 1000000. Is it good? Edit: It is too slow, now I get from 'checker': "time limit exceeded" –  Apr 10 '20 at 06:15
  • It will be a good idea but I have to modify last for loop, because it is iterating the whole vector. How to only iterate these indexes which have values? –  Apr 10 '20 at 06:25
  • With a million elements and `sort(p.begin(),p.end())`, you sort, probably, close to a million zeros for short input lists. Keep track of hoe many items are actually added and `sort(p.begin(),b.begin()+num_items)`. That said, you can also `reserve(1000000)` and `push_back` to make `b` keep count for you so that `sort(p.begin(),p.end())` make sense. – user4581301 Apr 10 '20 at 06:25
  • But these elements can be in whole vector, how to remove all 0 from this vector? –  Apr 10 '20 at 06:35

1 Answers1

0

I don't know what algorithm you are trying to implement, can you say what it is. It looks something similar to a median.

However, I'm sure the statement p[m]++ should be p[i]=m because it looks that you are trying to populate your vector with the values entered by the user.

Phillip Ngan
  • 15,482
  • 8
  • 63
  • 79
  • Look at the comment section. It is not important what is doing. We already know why I get `run time error` but now we are searching for the best solution to solve it. –  Apr 10 '20 at 06:44
  • @chris The question in its current form is about the run.-time error you get. If you want to ask about something else (like the "best" solution to some problem) then please ask a new question about it. But before that please read [ask], as well as [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). – Some programmer dude Apr 10 '20 at 06:55