Link to problem: CSES - Corner Subgrid Check
I tried solving it by comparing rows split by letter with AND operation using a bitset and using long long’s split into blocks, both with TLE! It is maddening. Is my implementation bad or is there a different approach to the problem I’m simply missing?
Code:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll block_size = 62;
ll a[30][3010][70];
ll cnt_corners(ll x, ll y) {
return __builtin_popcountll(x&y);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
char c;
cin >> n >> k;
for(ll i = 0; i < n; i++) {
for(ll j = 0; j < n; j++) {
cin >> c;
a[toupper(c) - 'A'][i][j/block_size] |= (1ll << (j%block_size));
}
}
for(ll x = 0; x < k; x++) {
for(ll i = 0; i < n-1; i++) {
for(ll y = i+1; y < n; y++) {
ll cnt = 0;
for(ll j = 0; j <= (n + block_size - 1) / block_size; j++) {
cnt += cnt_corners(a[x][i][j], a[x][y][j]);
if(cnt >= 2) {
cout << "YES\n";
goto l1;
}
}
}
}
cout << "NO\n";
l1: ;
}
return 0;
}