oj.uz

Submission #840020

# Submission time Handle Problem Language Result Execution time Memory
840020 2023-08-31T01:23:31 Z Benq Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 58256 KB 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;

using ll = long long;
using db = long double;  // or double, if TL is tight
using str = string;      // yay python!

// pairs
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
#define mp make_pair
#define f first
#define s second

#define tcT template <class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT > using V = vector<T>;
tcT, size_t SZ > using AR = array<T, SZ>;
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;

// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()

#define lb lower_bound
#define ub upper_bound
tcT > int lwb(V<T> &a, const T &b) { return int(lb(all(a), b) - bg(a)); }
tcT > int upb(V<T> &a, const T &b) { return int(ub(all(a), b) - bg(a)); }

// loops
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define each(a, x) for (auto &a : x)

const int MOD = (int)1e9 + 7;  // 998244353;
const int MX = (int)2e5 + 5;
const ll BIG = 1e18;  // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};  // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

// bitwise ops
// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
constexpr int pct(int x) { return __builtin_popcount(x); }  // # of bits set
constexpr int bits(int x) {  // assert(x >= 0); // make C++11 compatible until
	                         // USACO updates ...
	return x == 0 ? 0 : 31 - __builtin_clz(x);
}  // floor(log2(x))
constexpr int p2(int x) { return 1 << x; }
constexpr int msk2(int x) { return p2(x) - 1; }

ll cdiv(ll a, ll b) {
	return a / b + ((a ^ b) > 0 && a % b);
}  // divide a by b rounded up
ll fdiv(ll a, ll b) {
	return a / b - ((a ^ b) < 0 && a % b);
}  // divide a by b rounded down

tcT > bool ckmin(T &a, const T &b) {
	return b < a ? a = b, 1 : 0;
}  // set a = min(a,b)
tcT > bool ckmax(T &a, const T &b) {
	return a < b ? a = b, 1 : 0;
}  // set a = max(a,b)

tcTU > T fstTrue(T lo, T hi, U f) {
	++hi;
	assert(lo <= hi);  // assuming f is increasing
	while (lo < hi) {  // find first index such that f is true
		T mid = lo + (hi - lo) / 2;
		f(mid) ? hi = mid : lo = mid + 1;
	}
	return lo;
}
tcTU > T lstTrue(T lo, T hi, U f) {
	--lo;
	assert(lo <= hi);  // assuming f is decreasing
	while (lo < hi) {  // find first index such that f is true
		T mid = lo + (hi - lo + 1) / 2;
		f(mid) ? lo = mid : hi = mid - 1;
	}
	return lo;
}
tcT > void remDup(vector<T> &v) {  // sort and remove duplicates
	sort(all(v));
	v.erase(unique(all(v)), end(v));
}
tcTU > void safeErase(T &t, const U &u) {
	auto it = t.find(u);
	assert(it != end(t));
	t.erase(it);
}

inline namespace IO {
#define SFINAE(x, ...)                                                         \
	template <class, class = void> struct x : std::false_type {};              \
	template <class T> struct x<T, std::void_t<__VA_ARGS__>> : std::true_type {}

SFINAE(DefaultI, decltype(std::cin >> std::declval<T &>()));
SFINAE(DefaultO, decltype(std::cout << std::declval<T &>()));
SFINAE(IsTuple, typename std::tuple_size<T>::type);
SFINAE(Iterable, decltype(std::begin(std::declval<T>())));

template <class T> constexpr char Space(const T &) {
	return (Iterable<T>::value or IsTuple<T>::value) ? '\n' : ' ';
}

template <auto &is> struct Reader {
	template <class T> void Impl(T &t) {
		if constexpr (DefaultI<T>::value) is >> t;
		else if constexpr (Iterable<T>::value) {
			for (auto &x : t) Impl(x);
		} else if constexpr (IsTuple<T>::value) {
			std::apply([this](auto &...args) { (Impl(args), ...); }, t);
		} else static_assert(IsTuple<T>::value, "No matching type for read");
	}
	template <class... Ts> void read(Ts &...ts) { ((Impl(ts)), ...); }
};

template <class... Ts> void re(Ts &...ts) { Reader<cin>{}.read(ts...); }
#define def(t, args...)                                                        \
	t args;                                                                    \
	re(args);

template <auto &os, bool debug> struct Writer {
	string comma() const { return debug ? "," : ""; }
	template <class T> void Impl(T const &t) const {
		if constexpr (DefaultO<T>::value) os << t;
		else if constexpr (Iterable<T>::value) {
			if (debug) os << '{';
			int i = 0;
			for (auto &&x : t)
				((i++) ? (os << comma() << Space(x), Impl(x)) : Impl(x));
			if (debug) os << '}';
		} else if constexpr (IsTuple<T>::value) {
			if (debug) os << '(';
			std::apply(
			    [this](auto const &...args) {
				    int i = 0;
				    (((i++) ? (os << comma() << " ", Impl(args)) : Impl(args)),
				     ...);
			    },
			    t);
			if (debug) os << ')';
		} else static_assert(IsTuple<T>::value, "No matching type for print");
	}
	template <class T> void ImplWrapper(T const &t) const {
		if (debug) os << "\033[0;31m";
		Impl(t);
		if (debug) os << "\033[0m";
	}
	template <class... Ts> void print(Ts const &...ts) const {
		((Impl(ts)), ...);
	}
	template <class F, class... Ts>
	void print_with_sep(const std::string &sep, F const &f,
	                    Ts const &...ts) const {
		ImplWrapper(f), ((os << sep, ImplWrapper(ts)), ...), os << '\n';
	}
	void print_with_sep(const std::string &) const { os << '\n'; }
};

template <class... Ts> void pr(Ts const &...ts) {
	Writer<cout, false>{}.print(ts...);
}
template <class... Ts> void ps(Ts const &...ts) {
	Writer<cout, false>{}.print_with_sep(" ", ts...);
}
}  // namespace IO

inline namespace Debug {
template <typename... Args> void err(Args... args) {
	Writer<cerr, true>{}.print_with_sep(" | ", args...);
}

void err_prefix(str func, int line, string args) {
	cerr << "\033[0;31m\u001b[1mDEBUG\033[0m"
	     << " | "
	     << "\u001b[34m" << func << "\033[0m"
	     << ":"
	     << "\u001b[34m" << line << "\033[0m"
	     << " - "
	     << "[" << args << "] = ";
}

#ifdef LOCAL
#define dbg(args...) err_prefix(__FUNCTION__, __LINE__, #args), err(args)
#else
#define dbg(...)
#endif

const auto beg_time = std::chrono::high_resolution_clock::now();
// https://stackoverflow.com/questions/47980498/accurate-c-c-clock-on-a-multi-core-processor-with-auto-overclock?noredirect=1&lq=1
double time_elapsed() {
	return chrono::duration<double>(std::chrono::high_resolution_clock::now() -
	                                beg_time)
	    .count();
}
}  // namespace Debug

inline namespace FileIO {
void setIn(str s) { freopen(s.c_str(), "r", stdin); }
void setOut(str s) { freopen(s.c_str(), "w", stdout); }
void setIO(str s = "") {
	cin.tie(0)->sync_with_stdio(0);  // unsync C / C++ I/O streams
	cout << fixed << setprecision(12);
	// cin.exceptions(cin.failbit);
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) setIn(s + ".in"), setOut(s + ".out");  // for old USACO
}
}  // namespace FileIO

#include "soccer.h"

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
	V<V<pair<pi, int>>> ncol(N), col;
	int ans = 0;
	auto add_seg = [&](int idx, pi ival, int val) {
		ncol.at(idx).pb({ival, val});
		ckmax(ans, val);
	};
	F0R(i, N) {
		for (int j = 0; j < N;) {
			if (F[i][j]) {
				++j;
				continue;
			}
			int orig_j = j;
			while (j < N && !F[i][j]) ++j;
			add_seg(i, {orig_j, j - 1}, j - orig_j);
		}
	}
	swap(col, ncol);
	while (sz(col) > 1) {
		ncol.clear();
		ncol.rsz(sz(col) - 1);
		F0R(i, sz(col) - 1) {
			int l0 = 0, l1 = 0;
			while (l0 < sz(col[i]) && l1 < sz(col[i + 1])) {
				int lo = max(col[i][l0].f.f, col[i + 1][l1].f.f);
				int hi = min(col[i][l0].f.s, col[i + 1][l1].f.s);
				if (lo <= hi) {
					add_seg(i, {lo, hi},
					        max(col[i][l0].s, col[i + 1][l1].s) + hi - lo + 1);
				}
				if (col[i][l0].f.s < col[i + 1][l1].f.s) ++l0;
				else ++l1;
			}
		}
		swap(col, ncol);
	}
	return ans;
	// ps(ans);
	// R0F(i, N+1)
	// int max_ans = 0;
	// F0R(i, N) F0R(j, N) if (!F[i][j]) {
	// 	int ans = 0;
	// 	F0R(a, N) F0R(b, N) if (emp(a, i, b, j))++ ans;
	// 	ckmax(max_ans, ans);
	// }
	// return max_ans;
}

Compilation message

soccer.cpp: In function 'void FileIO::setIn(str)':
soccer.cpp:242:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  242 | void setIn(str s) { freopen(s.c_str(), "r", stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp: In function 'void FileIO::setOut(str)':
soccer.cpp:243:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  243 | void setOut(str s) { freopen(s.c_str(), "w", stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok
2 Correct 1 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 0 ms 212 KB ok
5 Correct 0 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 2 ms 340 KB ok
8 Correct 20 ms 2328 KB ok
9 Correct 312 ms 31908 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok
2 Correct 1 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 1 ms 212 KB ok
5 Correct 0 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 0 ms 212 KB ok
8 Correct 0 ms 212 KB ok
9 Correct 0 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 0 ms 212 KB ok
12 Correct 0 ms 212 KB ok
13 Correct 0 ms 212 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 0 ms 212 KB ok
5 Correct 1 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 0 ms 212 KB ok
8 Correct 0 ms 212 KB ok
9 Correct 0 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 0 ms 212 KB ok
12 Correct 0 ms 212 KB ok
13 Correct 0 ms 212 KB ok
14 Correct 0 ms 212 KB ok
15 Correct 0 ms 212 KB ok
16 Correct 0 ms 212 KB ok
17 Correct 0 ms 212 KB ok
18 Correct 0 ms 212 KB ok
19 Correct 0 ms 212 KB ok
20 Correct 0 ms 212 KB ok
21 Correct 0 ms 212 KB ok
22 Correct 0 ms 212 KB ok
23 Correct 0 ms 212 KB ok
24 Correct 0 ms 212 KB ok
25 Correct 0 ms 212 KB ok
26 Correct 0 ms 212 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 0 ms 212 KB ok
5 Correct 0 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 0 ms 212 KB ok
9 Correct 0 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 0 ms 212 KB ok
12 Correct 0 ms 212 KB ok
13 Correct 0 ms 212 KB ok
14 Correct 0 ms 212 KB ok
15 Correct 0 ms 212 KB ok
16 Correct 0 ms 212 KB ok
17 Correct 0 ms 212 KB ok
18 Correct 0 ms 212 KB ok
19 Correct 0 ms 212 KB ok
20 Correct 0 ms 212 KB ok
21 Correct 0 ms 212 KB ok
22 Correct 0 ms 212 KB ok
23 Correct 0 ms 212 KB ok
24 Correct 0 ms 212 KB ok
25 Correct 0 ms 212 KB ok
26 Correct 0 ms 212 KB ok
27 Correct 0 ms 212 KB ok
28 Correct 0 ms 212 KB ok
29 Correct 0 ms 212 KB ok
30 Correct 1 ms 212 KB ok
31 Correct 0 ms 212 KB ok
32 Correct 0 ms 212 KB ok
33 Correct 0 ms 212 KB ok
34 Correct 0 ms 212 KB ok
35 Correct 0 ms 212 KB ok
36 Correct 0 ms 212 KB ok
37 Correct 0 ms 212 KB ok
38 Correct 0 ms 212 KB ok
39 Correct 0 ms 212 KB ok
40 Correct 0 ms 212 KB ok
41 Correct 0 ms 212 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 0 ms 212 KB ok
5 Correct 0 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 0 ms 212 KB ok
9 Correct 0 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 0 ms 212 KB ok
12 Correct 0 ms 212 KB ok
13 Correct 0 ms 212 KB ok
14 Correct 0 ms 212 KB ok
15 Correct 0 ms 212 KB ok
16 Correct 0 ms 212 KB ok
17 Correct 0 ms 212 KB ok
18 Correct 0 ms 212 KB ok
19 Correct 0 ms 212 KB ok
20 Correct 0 ms 212 KB ok
21 Correct 0 ms 212 KB ok
22 Correct 0 ms 212 KB ok
23 Correct 0 ms 212 KB ok
24 Correct 0 ms 212 KB ok
25 Correct 0 ms 212 KB ok
26 Correct 0 ms 212 KB ok
27 Correct 0 ms 212 KB ok
28 Correct 0 ms 212 KB ok
29 Correct 0 ms 212 KB ok
30 Correct 1 ms 212 KB ok
31 Correct 0 ms 212 KB ok
32 Correct 0 ms 212 KB ok
33 Correct 0 ms 212 KB ok
34 Correct 0 ms 212 KB ok
35 Correct 0 ms 212 KB ok
36 Correct 0 ms 212 KB ok
37 Correct 0 ms 212 KB ok
38 Correct 0 ms 212 KB ok
39 Correct 0 ms 212 KB ok
40 Correct 0 ms 212 KB ok
41 Correct 0 ms 212 KB ok
42 Correct 41 ms 4180 KB ok
43 Correct 31 ms 3992 KB ok
44 Correct 144 ms 4256 KB ok
45 Correct 176 ms 3708 KB ok
46 Correct 61 ms 4372 KB ok
47 Correct 32 ms 2388 KB ok
48 Correct 21 ms 2260 KB ok
49 Correct 20 ms 2260 KB ok
50 Correct 439 ms 5292 KB ok
51 Correct 22 ms 2712 KB ok
52 Correct 20 ms 2324 KB ok
53 Correct 18 ms 2200 KB ok
54 Correct 19 ms 2328 KB ok
55 Correct 23 ms 2460 KB ok
56 Correct 18 ms 2260 KB ok
57 Correct 27 ms 2324 KB ok
58 Correct 20 ms 2328 KB ok
59 Correct 23 ms 2324 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 0 ms 212 KB ok
5 Correct 0 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 0 ms 212 KB ok
8 Correct 2 ms 340 KB ok
9 Correct 20 ms 2328 KB ok
10 Correct 312 ms 31908 KB ok
11 Correct 0 ms 212 KB ok
12 Correct 1 ms 212 KB ok
13 Correct 0 ms 212 KB ok
14 Correct 0 ms 212 KB ok
15 Correct 0 ms 212 KB ok
16 Correct 0 ms 212 KB ok
17 Correct 0 ms 212 KB ok
18 Correct 0 ms 212 KB ok
19 Correct 0 ms 212 KB ok
20 Correct 0 ms 212 KB ok
21 Correct 0 ms 212 KB ok
22 Correct 0 ms 212 KB ok
23 Correct 0 ms 212 KB ok
24 Correct 0 ms 212 KB ok
25 Correct 0 ms 212 KB ok
26 Correct 0 ms 212 KB ok
27 Correct 0 ms 212 KB ok
28 Correct 0 ms 212 KB ok
29 Correct 0 ms 212 KB ok
30 Correct 0 ms 212 KB ok
31 Correct 0 ms 212 KB ok
32 Correct 0 ms 212 KB ok
33 Correct 0 ms 212 KB ok
34 Correct 0 ms 212 KB ok
35 Correct 1 ms 212 KB ok
36 Correct 0 ms 212 KB ok
37 Correct 0 ms 212 KB ok
38 Correct 0 ms 212 KB ok
39 Correct 0 ms 212 KB ok
40 Correct 0 ms 212 KB ok
41 Correct 0 ms 212 KB ok
42 Correct 0 ms 212 KB ok
43 Correct 0 ms 212 KB ok
44 Correct 0 ms 212 KB ok
45 Correct 0 ms 212 KB ok
46 Correct 0 ms 212 KB ok
47 Correct 41 ms 4180 KB ok
48 Correct 31 ms 3992 KB ok
49 Correct 144 ms 4256 KB ok
50 Correct 176 ms 3708 KB ok
51 Correct 61 ms 4372 KB ok
52 Correct 32 ms 2388 KB ok
53 Correct 21 ms 2260 KB ok
54 Correct 20 ms 2260 KB ok
55 Correct 439 ms 5292 KB ok
56 Correct 22 ms 2712 KB ok
57 Correct 20 ms 2324 KB ok
58 Correct 18 ms 2200 KB ok
59 Correct 19 ms 2328 KB ok
60 Correct 23 ms 2460 KB ok
61 Correct 18 ms 2260 KB ok
62 Correct 27 ms 2324 KB ok
63 Correct 20 ms 2328 KB ok
64 Correct 23 ms 2324 KB ok
65 Correct 619 ms 58256 KB ok
66 Correct 350 ms 49824 KB ok
67 Correct 308 ms 38552 KB ok
68 Execution timed out 4571 ms 53768 KB Time limit exceeded
69 Halted 0 ms 0 KB -