Блог пользователя djay24

Автор djay24, история, 21 месяц назад, По-английски

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 :)

  • Проголосовать: нравится
  • -15
  • Проголосовать: не нравится

»
21 месяц назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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