Genius3435's blog

By Genius3435, history, 7 weeks ago, In English

I was doing a Div 3 round (#686, contest id 1454), and when I made my solution for problem C, I found this weird bug that I can't for the life of me find the cause of.

Here is the code:


#include <algorithm> #include <iostream> #include <vector> #include <map> using namespace std; #define all(v) v.begin(), v.end() int main() { int T; cin >> T; while (T--) { int N, I = 1; cin >> N; map<int, pair<int, int> > ids; int a[N]; cout << "Making ids: \n"; for (int i = 0; i < N; i++) { cin >> a[i]; if (!ids[a[i]].first) { cout << "C: " << a[i] << ' ' << I << '\n'; ids[a[i]] = make_pair(I, 0); I++; } a[i] = ids[a[i]].first; ids[a[i]].second++; if (!ids[a[i]].first) cout << "ERROR "; cout << ids[a[i]].first << ' ' << ids[a[i]].second << '\n'; } cout << "\nChecking ids of 1, 2, and 3:\n"; cout << ids[1].second << ' ' << ids[2].second << ' ' << ids[3].second << '\n'; cout << "\nChecking all ids:\n"; for (int i = 0; i < N; i++) cout << a[i] << ' ' << ids[a[i]].second << '\n'; cout << "\n\n"; cout << "First guy: " << ids[a[0]].second << endl; cout << "Last guy: " << ids[a[N - 1]].second << endl; ids[a[0]].second--; ids[a[N - 1]].second--; cout << "New First guy: " << ids[a[0]].second << endl; cout << "New Last guy: " << ids[a[N - 1]].second << endl; // cout << a[0] << ' ' << a[1] << endl; for (int i = 1; i < N; i++) if (a[i] == a[i - 1]) { cout << a[i] << ' ' << a[i - 1] << ' ' << ids[a[i]].second << '\n'; ids[a[i]].second--; } cout << '\n'; int M = 2e9; for (const auto &p: ids) { cout << p.second.first << ' ' << p.second.second << '\n'; M = min(M, p.second.second); } cout << M + 1 << "\n\n"; } }

I know it's long, and there's almost certainly a much easier solution, but this is what I got.

I'm using the map for something similar to coordinate compression, because I thought it was easier than having to initialize a 2e5-long array for the numbers.

The problem is that when I test it on this case: 11 2 2 1 2 3 2 1 2 3 1 2

The map somehow makes an index of 0 for the first two 2s. What's weird is that after the first two, everything else works. I thought it may be a bug when two of the same number are next to one another, but I don't see anything that could cause that in my code. Also, it works on the other test cases in the sample test, which also have consecutive equal numbers. Another thing I find weird is that when I print out the values in the array/map later in my program, the 0s don't show up. Then I thought maybe it was an error with the map.size() function, so I used a separate variable (called I) to set the value, but that didn't work.

Can someone please look over my code and help me find the problem? If you have any questions for why I have certain lines of code, just put a comment, and I'll try to reply ASAP!

Also, this is my first blog, so please help me on how I can improve my CF blog-writing.

 
 
 
 
  • Vote: I like it
  • -21
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

From here:

std::map<>::operator[]

Returns a reference to the value that is mapped to a key equivalent to key, performing an insertion if such key does not already exist.
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That makes sense, but it only seems to happen on this one test case. So then how would I check if the kay hasn't been used yet? Keep a set of the numbers used so far and check if it's in it? That seems tedious though, so I'm not sure if there's a better method.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      if (auto it = map.find(key); it != map.end()) {
        // key is in use
      } else {
        // key is missing
      }
      
      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks! I'll put this into my code and check if it works.

        Also, do you know why this blog has a score of -21? Just people being toxic and downvoting every blog they see, or is it because my question made me sound like a noob?