Hi everyone.

This is my template for debugging in C++. I was inspired by Tourist's source code and modified it to my style. Here is it:

#include <bits/stdc++.h>

using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

To debug, just type: debug(x, y, z...). It requires C++ 11 or above.

It can work with:

• Primitive data types: bool, int, long long, float, ...

• std::pair, std::string

• Collection types: std::vector, std::map, std::set, ...
• Expressions

It also support multiple arguments.

How to use

Primitive data types:

bool a = true;
debug(a);

int b = 1;
float c = 2.5;
long long d = LLONG_MAX;
char e = 'e';
debug(a, b, c, d, e);

Output:
'[a] = [true]'
'[a, b, c, d, e] = [true, 1, 2.5, 9223372036854775807, 'e']'

std::pair and std::string:

pair<int, int> a = {1, 2};
pair<string, bool> b = {"abcd", false};
pair<char, float> c = {'x', 0.5};
string d = "This is a string";
pair<int, pair<int, int> > e = {1, {2, 3}};
debug(a, b, c, d, e);

Output:
'[a, b, c, d, e] = [{1, 2}, {"abcd", false}, {'x', 0.5}, "This is a string", {1, {2, 3}}]'

Note: You should only debug a pair of simple data types. For example, the debug won't work if one of pair's elements is collection type (std::vector, std::map, std::set...).

Collection types:

Basically, the debug works with collections types which you can iterate by for (auto i: a). So the debugger won't work with collection types like std::queue or std::stack.

vector<int> a = {1, 2, 3, 4};
set<int> b = {1, 2, 2, 3, 3, 4, 4, 5};
map<string, int> c;
c["string 1"] = 1;
c["string 2"] = 2;
debug(a, b, c);

unordered_map<string, int> d;
d["string 3"] = 3;
d["string 4"] = 4;
multiset<int> e = {5, 5, 4, 3, 1, 1, 2};
vector<vector<int> > f = {{1, 2, 3}};
debug(d, e, f);

Output:
'[a, b, c] = [{1, 2, 3, 4}, {1, 2, 3, 4, 5}, {{"string 1", 1}, {"string 2", 2}}]'
'[d, e, f] = [{{"string 4", 4}, {"string 3", 3}}, {1, 1, 2, 3, 4, 5, 5}, {{1, 2, 3}}]'

Note: I haven't tried the debug with other complex data types nested in collection types.

int a = 1;
int b = 2;
debug(a + b, a * b, a / b, a - b, a / (float)b, 2019, 2019 - 1);

Output:
'[a + b, a * b, a / b, a - b, a / (float)b, 2019, 2019 - 1] = [3, 2, 0, -1, 0.5, 2019, 2018]'

You can use the template and change it's style to what you want. Hope it would help you debug in C++ easier.

(Sorry for my bad english!!)

Problem (QBSEGPAR — Vietnam Olympiad of Informatics 2005): For an integer array a₁, a₂, ..., a_n and a integer k. Determine the smallest integer M to divide the array into k non-empty parts so that the sum of the elements in each parts does not exceed M.

• Constraints: k ≤ n ≤ 15000, |a_i| ≤ 30000.

UPD: For example, we have n = 5, k = 3, and the array is 4, 3, 2, 1, 5. Then here is one way to divide the array into 3 parts: [4, 3], [2], [1, 5]. You can also represent one way to divide the array into k parts by an array x₁, x₂, ..., x_k (1 ≤ x₁ < x₂ < ... < x_k = n) which part i^th (i > 1) is subarray [x_i - 1 + 1..x_i] (first part is subarray [1..x₁]).

I have an solution, which we do binary seaching for M, and dp to check if this M could satisfy (let f(i, j) = true means you could divide array a[1..i] into j parts so that the sum of the elements in each of j parts does not exceed M. Otherwise, f(i, j) = false. Then we can divide array a[1..n] into k satisfied parts if f(n, k) = true). Of course this couldn't pass all tests.

Then I checked for the solution. Here is it, we also do binary searching for M, but for each M, we do a different dp:

• f_i = minimum number of parts which has sum of elements does not exceed M that you could divide from array a[1..i].
• g_i = maximum number of parts which has sum of elements does not exceed M that you could divide from array a[1..i].

Required complexity is o(nlogn²). We can calculate f and g by o(nlogn) dp, which need segment tree or Fenwick tree (i haven't done it), or simple o(n²) dp. Okay, now here is the checking part, which is unclear to me: The solution said that array a[1..n] could divide into k satisfied parts if f_n ≤ k ≤ g_n. I think this might not be right. In my opinion, we can divide array a[1..n] into minimum f_n satisfied parts, maximum g_n satisfied parts, but it doesn't mean we can divide the array into k satisfied parts which f_n ≤ k ≤ g_n.

Could you tell me how to prove this solution right or wrong? Thanks for your help!