djay24's blog

By djay24, history, 21 month(s) ago, In English

While up solving F — Dasha and Nightmares I came across an unusual error. It's been more than six months now I'm practicing writing #define int long long int pragma at the start of my code, I never faced any issues except today.

I submitted 2 codes, when I write #define int long long int it's giving MLE error but if I removed that line it's getting accepted. I'm using GNU C++20 (64). Although both code are running fine in my sublime text editor.

MLE :

#include <bits/stdc++.h>
#define int long long int

const int MAXN = 26;
int cnt[1 << MAXN];

void solve(){

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n; 
    std::cin >> n;
 
    std::vector<std::pair <int, int>> vals;

    for (int i = 0; i < n; i++) {
        std::string s; 
        std::cin >> s;
        int cor = 0, cxor = 0;
        for (char c : s) {
            int v = (c - 'a');
            cor = cor | (1 << v);
            cxor = cxor ^ (1 << v);
        }
        vals.push_back({cor, cxor});
    }
 
    int ans = 0;
  
    for (int i = 0; i < 26; i++) {
        int goal = ((1 << 26) - 1) ^ (1 << i);
 
        for (auto [cor, cxor] : vals) {
            if (cor & (1 << i)) continue;
            ans += cnt[cxor ^ goal];
            cnt[cxor] += 1;
        }

        for (auto [cor, cxor] : vals) {
            if (cor & (1 << i)) continue;
            cnt[cxor] -= 1;
        }
    }

    std::cout << ans << "\n";

}
     
signed main() {

    int t = 1;
    //std::cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }
}

AC :

#include <bits/stdc++.h>

const int MAXN = 26;
int cnt[1 << MAXN];

void solve(){

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n; 
    std::cin >> n;
 
    std::vector<std::pair <int, int>> vals;

    for (int i = 0; i < n; i++) {
        std::string s; 
        std::cin >> s;
        int cor = 0, cxor = 0;
        for (char c : s) {
            int v = (c - 'a');
            cor = cor | (1 << v);
            cxor = cxor ^ (1 << v);
        }
        vals.push_back({cor, cxor});
    }
 
    long long ans = 0;
  
    for (int i = 0; i < 26; i++) {
        int goal = ((1 << 26) - 1) ^ (1 << i);
 
        for (auto [cor, cxor] : vals) {
            if (cor & (1 << i)) continue;
            ans += cnt[cxor ^ goal];
            cnt[cxor] += 1;
        }

        for (auto [cor, cxor] : vals) {
            if (cor & (1 << i)) continue;
            cnt[cxor] -= 1;
        }
    }

    std::cout << ans << "\n";

}
     
signed main() {

    int t = 1;
    //std::cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }
}

Is there any downsides of using #int long long int ? I have seen AwakeAnay using #define int long long int, maybe you can help me ! Also this code I have taken from BucketPotato, can you help ?

What practice should be followed in general so there is not an integer overflow ?

Thank you :)

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

»
21 month(s) ago, # |
  Vote: I like it +12 Vote: I do not like it

i guess the problem is that #define int long long int allocates 64 bits of memory to every integer, while in the ac solution memory is used more carefully, allocating 64 bits only when needed and 32 otherwise

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you, it was really a stupid silly mistake. I was scratching my head all day today, lol.