Submission #1172606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172606		perchuts	Rectangles (IOI19_rect)	C++20	0 / 100	0 ms	328 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 3e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rnd(int l, int r) {
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}

long long solve01(vector<vector<int>> a) {
    int n = sz(a), m = sz(a[0]);
    vector<vector<int>> h(n, vector<int>(m));
	for (int j = 0; j < m; ++j) h[0][j] = a[0][j] ^ 1;
    for (int i = 1; i < n; ++i) for (int j = 0; j < m; ++j) {
        if (a[i][j] == 1) h[i][j] = 0;
        else h[i][j] = 1 + h[i-1][j];
    }
    int ans = 0;
	//for (auto x : h) {
	//	for (auto y : x) cout << y << ' ';
	//	cout << endl;
	//}
	// its actually way easier than this
    for (int i = 1; i < n-1; ++i) {
		for (int l = 0, r = 0; l < m; l = r) {
			if (a[i][r]) r++;
			else {
				cout.flush();
				int ok = (h[i][r] <= i);
				while (a[i][r] == 0) ok &= (h[i][r] == h[i][l] and a[i+1][r]), r++;
				ans += ok;
			}
		}
    }
    return ans;
}
long long count_rectangles(vector<vector<int> > a) {
#define int ll
    int n = sz(a), m = sz(a[0]), mx = 0;
    for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) ckmax(mx, a[i][j]);
    if (mx <= 1) return solve01(a);
#undef int
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:63:1: warning: control reaches end of non-void function [-Wreturn-type]
   63 | }
      | ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28