Blog entries - Codeforces

I was stuck on this CSES question : Corner Subgrid Count for nearly 2 months, when I had already got the approach at the first view only. (It's not that I have been trying daily since the last 2 months, I got TLE and I left... bruhh — )

And I just figured out that I was not using the correct compile-time optimization (bruh-, what the hell was that). I was trying with Ofast and O3 optimizations but just do popcnt optimization and you are done. My approach (as obvious) was just break each row into bits of size 64, do pairwise-AND and tally the number of bits set in the pairwise-ANDs. Finally, add (count*(count — 1))/2 to the ans.

But I am amazed to see that how powerful a tool pragma actually is and how it can make your life easy :

TLE-ed Code

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
 
#define int long long int
#define ull unsigned long long
 
//std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
 
constexpr int V = 1E9;
constexpr int MAXN=1e9;
const int mod=998244353;
 
void solve() 
{
    int n;
    cin >> n ;
    vector<string> v(n);
    for(int i=0; i<n; i++) cin>>v[i];
    int m = v[0].size();
    int B = (m + 63) / 64; 
    vector<vector<unsigned long long>> vals(n, vector<unsigned long long>(B, 0ULL));
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (v[i][j] == '1') {
                int b = j >> 6;          // j / 64
                int off = j & 63;        // j % 64
                vals[i][b] |= (1ULL << off);
            }
        }
    }
    // for(auto x: vals)
    // {
    //     for(auto y : x) cout<<y<<" ";
    //     cout<<endl;
    // }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        const ull *Ai = vals[i].data();
        for (int j = i + 1; j < n; ++j) {
            const ull *Aj = vals[j].data();
            int cnt = 0;
            for (int z = 0; z < B; ++z) {
                cnt += __builtin_popcountll(Ai[z] & Aj[z]);
            }
            if (cnt >= 2) ans += 1LL * cnt * (cnt - 1) / 2;
        }
    }
    cout<<ans<<endl;
}
 
int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    //auto begin = std::chrono::high_resolution_clock::now();
    //freopen("piggyback.in", "r", stdin);
    //freopen("piggyback.out", "w", stdout);
    int t=1;
    //cin >> t;
    
    while (t--) 
    {
        solve();
    }
    // auto end = std::chrono::high_resolution_clock::now();
    // auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    // cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
    return 0;
}

Accepted Code

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC target("popcnt")
 
#define int long long int
#define ull unsigned long long
 
//std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
 
constexpr int V = 1E9;
constexpr int MAXN=1e9;
const int mod=998244353;
 
void solve() 
{
    int n;
    cin >> n ;
    vector<string> v(n);
    for(int i=0; i<n; i++) cin>>v[i];
    int m = v[0].size();
    int B = (m + 63) / 64; 
    vector<vector<unsigned long long>> vals(n, vector<unsigned long long>(B, 0ULL));
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (v[i][j] == '1') {
                int b = j >> 6;          // j / 64
                int off = j & 63;        // j % 64
                vals[i][b] |= (1ULL << off);
            }
        }
    }
    // for(auto x: vals)
    // {
    //     for(auto y : x) cout<<y<<" ";
    //     cout<<endl;
    // }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        const ull *Ai = vals[i].data();
        for (int j = i + 1; j < n; ++j) {
            const ull *Aj = vals[j].data();
            int cnt = 0;
            for (int z = 0; z < B; ++z) {
                cnt += __builtin_popcountll(Ai[z] & Aj[z]);
            }
            if (cnt >= 2) ans += 1LL * cnt * (cnt - 1) / 2;
        }
    }
    cout<<ans<<endl;
}
 
int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    //auto begin = std::chrono::high_resolution_clock::now();
    //freopen("piggyback.in", "r", stdin);
    //freopen("piggyback.out", "w", stdout);
    int t=1;
    //cin >> t;
    
    while (t--) 
    {
        solve();
    }
    // auto end = std::chrono::high_resolution_clock::now();
    // auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    // cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
    return 0;
}

If any of you got it Accepted without Pragma, I would love to hear that too

Full text and comments »

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	dXqwq	3436
8	Radewoosh	3415
9	Otomachi_Una	3413
10	Um_nik	3376

#	User	Contrib.
1	Qingyu	158
2	adamant	152
3	Um_nik	146
4	Dominater069	144
5	errorgorn	141
6	cry	139
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
9	TheScrasse	134

anaconda666's blog