CORNER SUBGRID COUNT CSES : PRAGMA TARGET(POPCNT) V/S PRAGMA O3 OPTIMIZATION

#	User	Rating
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3382
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

#	User	Contrib.
1	Qingyu	155
2	nik_exists	151
3	maspy	149
4	AmShZ	145
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	134
9	maroonrk	132
10	cry	130

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

	Rev.	Lang.	By	When	Δ	Comment
	en2		anaconda666	2025-09-21 12:24:21	111	Tiny change: 'd Code">\nTLE-ed code : \n\n~~~~~\n#include' -> 'd Code">\n#include'
	en1		anaconda666	2025-09-21 11:45:29	4991	Initial revision (published)

History