jainrishab26121's blog

By jainrishab26121, history, 2 hours ago, In English

Hey guys, please help me debug this code for d1 in today's contest, it got WA on test 24(you can imagine how I felt after seeing that during the contest). Here's the code:


ll mex2(vi a) { int n = a.size(); map<int,int>hash; loop(i , 0 , n - 1) { hash[a[i]]++; } ll cnt = 0 , i = 0; while(true) { if(hash[i] == 0) { if(cnt) { return i; } cnt++; } i++; } } void print(ll n) { cout << n << endl; } void solve() { ll n , m; cin >> n >> m; vector<vi>a(n); int s , temp; loop(i , 0 , n - 1) { cin >> s; loop(j , 0 , s - 1) { cin >> temp; a[i].push_back(temp); } } ll ans = 0; loop(i , 0 , n - 1) { ans = max(ans , mex2(a[i])); } int x = ans; ans *= min(ans + 1 , m + 1); if(x > m) { print(ans); return; } else { ans -=((x)*(x + 1))/2; ans += (m*(m + 1))/2; print(ans); } }

Also, I am sorry if this is not supposed to be here and there is a separate place for debugging related doubts. `

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

»
2 hours ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Seems like int overflow in ans -=((x)*(x + 1))/2;

Check the following:

int x=(1<<20); ll ans=x*x; cout<<ans<<'\n';

it outputs 0 instead of $$$2^{40}$$$.

  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Got it, thanks for the help.