xft's blog

By xft, history, 2 years ago, In English

So I was solving this problem recently 1468C, while solving I used two different codes which do the same simulation, but the first one which uses structured binding has some undefined behaviour which causes it to tle while the second one which doesn't use structured binding passes. I am not able to understand why this is happening ?

Code 1 :

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

#define int long long
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) static_cast<int>((x).size())


signed main() {

        ios::sync_with_stdio(false);
        cin.tie(nullptr);

        int q;
        cin >> q;
        
        int yet = 1, mi = 1;
        set<int> del;
        map<int, set<int>, greater<int>> m;
        while (q--) {
               int x;
               cin >> x;
               if (x == 1) {
                   cin >> x;
                   m[x].insert(yet);
                   yet++;
                   continue;
               }
               if (x == 2) {
                   while (del.count(mi)) mi++;
                   cout << mi << " ";
                   del.insert(mi);
               }
               if (x == 3) {
                   while (true) {
                          auto [p, y] = *m.begin();
                          if (!del.count(*y.begin())) {
                               cout << *y.begin() << " ";
                               del.insert(*y.begin());
                               break;
                          }
                          y.erase(y.begin());
                          if (!sz(y)) m.erase(m.begin());
                   } 
               }
        }
        
}

Code 2:

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

#define int long long
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) static_cast<int>((x).size())


signed main() {

        ios::sync_with_stdio(false);
        cin.tie(nullptr);

        int q;
        cin >> q;
        
        int yet = 1, mi = 1;
        set<int> del;
        map<int, set<int>, greater<int>> m;
        while (q--) {
               int x;
               cin >> x;
               if (x == 1) {
                   cin >> x;
                   m[x].insert(yet);
                   yet++;
                   continue;
               }
               if (x == 2) {
                   while (del.count(mi)) mi++;
                   cout << mi << " ";
                   del.insert(mi);
               }
               if (x == 3) {
                   while (true) {
                          int k = m.begin()->first;
                          if (!del.count(*m[k].begin())) {
                               cout << *m[k].begin() << " ";
                               del.insert(*m[k].begin());
                               break;
                          }
                          m[k].erase(m[k].begin());
                          if (!sz(m[k])) m.erase(m.begin());
                   } 
               }
        }
        
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

y in the first fragment is a copy of an element of map m. Erasing elements from y wouldn't change m.