oj.uz

Submission #840019

# Submission time Handle Problem Language Result Execution time Memory
840019 2023-08-31T01:21:40 Z Benq Soccer Stadium (IOI23_soccer) C++17
31 / 100
 566 ms 49872 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.f < col[i + 1][l1].f.f) ++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 1 ms 212 KB ok

Subtask #1
1.5 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB ok
2 Correct 0 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 1 ms 212 KB ok
7 Correct 2 ms 340 KB ok
8 Partially correct 19 ms 2260 KB partial
9 Partially correct 307 ms 31896 KB partial

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 1 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 1 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 1 ms 212 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 0 ms 212 KB ok
8 Correct 0 ms 212 KB ok
9 Correct 1 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 1 ms 212 KB ok
15 Correct 0 ms 212 KB ok
16 Correct 1 ms 212 KB ok
17 Partially correct 0 ms 212 KB partial
18 Correct 1 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
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 1 ms 212 KB ok
9 Correct 0 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 1 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 1 ms 212 KB ok
17 Correct 0 ms 212 KB ok
18 Correct 1 ms 212 KB ok
19 Partially correct 0 ms 212 KB partial
20 Correct 1 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 1 ms 212 KB ok
30 Partially correct 1 ms 212 KB partial
31 Partially correct 1 ms 212 KB partial
32 Partially correct 0 ms 212 KB partial
33 Correct 1 ms 212 KB ok
34 Correct 1 ms 212 KB ok
35 Correct 0 ms 212 KB ok
36 Correct 0 ms 212 KB ok
37 Correct 1 ms 212 KB ok
38 Correct 0 ms 212 KB ok
39 Correct 1 ms 212 KB ok
40 Correct 0 ms 212 KB ok
41 Correct 1 ms 212 KB ok

Subtask #5
4.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 1 ms 212 KB ok
9 Correct 0 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 1 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 1 ms 212 KB ok
17 Correct 0 ms 212 KB ok
18 Correct 1 ms 212 KB ok
19 Partially correct 0 ms 212 KB partial
20 Correct 1 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 1 ms 212 KB ok
30 Partially correct 1 ms 212 KB partial
31 Partially correct 1 ms 212 KB partial
32 Partially correct 0 ms 212 KB partial
33 Correct 1 ms 212 KB ok
34 Correct 1 ms 212 KB ok
35 Correct 0 ms 212 KB ok
36 Correct 0 ms 212 KB ok
37 Correct 1 ms 212 KB ok
38 Correct 0 ms 212 KB ok
39 Correct 1 ms 212 KB ok
40 Correct 0 ms 212 KB ok
41 Correct 1 ms 212 KB ok
42 Partially correct 19 ms 3028 KB partial
43 Partially correct 22 ms 3796 KB partial
44 Partially correct 18 ms 2388 KB partial
45 Partially correct 22 ms 2388 KB partial
46 Partially correct 19 ms 2644 KB partial
47 Partially correct 19 ms 2260 KB partial
48 Correct 25 ms 2388 KB ok
49 Correct 20 ms 2328 KB ok
50 Partially correct 21 ms 3028 KB partial
51 Partially correct 21 ms 2708 KB partial
52 Correct 20 ms 2328 KB ok
53 Correct 19 ms 2260 KB ok
54 Correct 19 ms 2328 KB ok
55 Correct 21 ms 2260 KB ok
56 Correct 19 ms 2332 KB ok
57 Correct 23 ms 2380 KB ok
58 Correct 23 ms 2260 KB ok
59 Correct 21 ms 2324 KB ok

Subtask #6
7.5 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 2 ms 340 KB ok
9 Partially correct 19 ms 2260 KB partial
10 Partially correct 307 ms 31896 KB partial
11 Correct 1 ms 212 KB ok
12 Correct 1 ms 212 KB ok
13 Correct 1 ms 212 KB ok
14 Correct 0 ms 212 KB ok
15 Correct 0 ms 212 KB ok
16 Correct 1 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 1 ms 212 KB ok
22 Correct 0 ms 212 KB ok
23 Correct 1 ms 212 KB ok
24 Partially correct 0 ms 212 KB partial
25 Correct 1 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 1 ms 212 KB ok
35 Partially correct 1 ms 212 KB partial
36 Partially correct 1 ms 212 KB partial
37 Partially correct 0 ms 212 KB partial
38 Correct 1 ms 212 KB ok
39 Correct 1 ms 212 KB ok
40 Correct 0 ms 212 KB ok
41 Correct 0 ms 212 KB ok
42 Correct 1 ms 212 KB ok
43 Correct 0 ms 212 KB ok
44 Correct 1 ms 212 KB ok
45 Correct 0 ms 212 KB ok
46 Correct 1 ms 212 KB ok
47 Partially correct 19 ms 3028 KB partial
48 Partially correct 22 ms 3796 KB partial
49 Partially correct 18 ms 2388 KB partial
50 Partially correct 22 ms 2388 KB partial
51 Partially correct 19 ms 2644 KB partial
52 Partially correct 19 ms 2260 KB partial
53 Correct 25 ms 2388 KB ok
54 Correct 20 ms 2328 KB ok
55 Partially correct 21 ms 3028 KB partial
56 Partially correct 21 ms 2708 KB partial
57 Correct 20 ms 2328 KB ok
58 Correct 19 ms 2260 KB ok
59 Correct 19 ms 2328 KB ok
60 Correct 21 ms 2260 KB ok
61 Correct 19 ms 2332 KB ok
62 Correct 23 ms 2380 KB ok
63 Correct 23 ms 2260 KB ok
64 Correct 21 ms 2324 KB ok
65 Partially correct 305 ms 43860 KB partial
66 Partially correct 341 ms 49872 KB partial
67 Partially correct 317 ms 38564 KB partial
68 Partially correct 317 ms 32020 KB partial
69 Partially correct 266 ms 33184 KB partial
70 Partially correct 296 ms 34840 KB partial
71 Partially correct 306 ms 32028 KB partial
72 Partially correct 303 ms 31948 KB partial
73 Correct 511 ms 31896 KB ok
74 Correct 329 ms 31964 KB ok
75 Correct 328 ms 31956 KB ok
76 Correct 326 ms 43932 KB ok
77 Partially correct 328 ms 43924 KB partial
78 Partially correct 334 ms 36300 KB partial
79 Correct 310 ms 34124 KB ok
80 Partially correct 302 ms 33612 KB partial
81 Correct 311 ms 33288 KB ok
82 Correct 320 ms 33456 KB ok
83 Partially correct 320 ms 40084 KB partial
84 Correct 296 ms 31764 KB ok
85 Correct 327 ms 31760 KB ok
86 Correct 299 ms 31892 KB ok
87 Correct 300 ms 31900 KB ok
88 Correct 288 ms 31828 KB ok
89 Correct 307 ms 31964 KB ok
90 Correct 330 ms 31912 KB ok
91 Correct 308 ms 31896 KB ok
92 Correct 316 ms 36252 KB ok
93 Correct 307 ms 37912 KB ok
94 Correct 297 ms 33484 KB ok
95 Correct 420 ms 32660 KB ok
96 Correct 302 ms 32404 KB ok
97 Correct 306 ms 32280 KB ok
98 Correct 297 ms 32028 KB ok
99 Partially correct 277 ms 36432 KB partial
100 Correct 336 ms 31892 KB ok
101 Correct 336 ms 31896 KB ok
102 Correct 342 ms 31896 KB ok
103 Correct 343 ms 31896 KB ok
104 Correct 349 ms 31896 KB ok
105 Correct 344 ms 31896 KB ok
106 Correct 367 ms 31888 KB ok
107 Correct 341 ms 31948 KB ok
108 Correct 450 ms 47436 KB ok
109 Correct 566 ms 47640 KB ok