Skip to content

Instantly share code, notes, and snippets.

@cgiosy

cgiosy/leetcode.cpp

Last active November 16, 2020 16:55
Show Gist options
  • Save cgiosy/66f0f68e3e82a78210f51910e8bfae20 to your computer and use it in GitHub Desktop.
Save cgiosy/66f0f68e3e82a78210f51910e8bfae20 to your computer and use it in GitHub Desktop.
Download ZIP
Leetcode test runner
Raw
leetcode.cpp
// LEETCODE
#include <bits/stdc++.h>
namespace leetcode {
#define __COUT_DEFAULT_DELIMITER__ ","
// #define __PARSE_INT128__
// #define __PARSE_CHAR_QUOTE__ '\'
// #define __PARSE_STRING_DELIMITER__ " ,]})"
// Console Output //
template<typename T, typename F, typename U, typename V, typename W = std::string_view>
std::ostream& print_iterable(
std::ostream& out,
const T& val,
const F func,
const U& start,
const V& end,
const W& delim = __COUT_DEFAULT_DELIMITER__
) {
out << start;
bool first = true;
for (const auto& item : val) {
if (!first)
out << delim;
func(item);
first = false;
}
out << end;
return out;
}
template<typename T, typename U>
std::ostream& operator<<(std::ostream& out, const std::pair<T, U>& val) {
out << "(" << val.first << ", " << val.second << ")";
return out;
}
template<typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& val) {
return print_iterable(out, val, [&](const T& item) {
out << item;
}, "[", "]");
}
template<typename K, typename V>
std::ostream& operator<<(std::ostream& out, const std::map<K, V>& val) {
return print_iterable(out, val, [&](const std::pair<K, V>& item) {
out << item.first << ": " << item.second;
}, "{", "}");
}
template<typename K, typename V>
std::ostream& operator<<(std::ostream& out, const std::unordered_map<K, V>& val) {
return print_iterable(out, val, [&](const std::pair<K, V>& item) {
out << item.first << ": " << item.second;
}, "{", "}");
}
// Parser //
#define PASRE_CHECK(...) /* do nothing */
void skip_whitespaces(const std::string_view& input, size_t& pos) {
while(true) {
PASRE_CHECK(pos < input.size());
if(!std::isspace(input[pos]))
break;
pos++;
}
}
template<typename T>
T&& parse(const std::string_view& input, size_t& pos, T&& result = T()) {
skip_whitespaces(input, pos);
PASRE_CHECK(pos < input.size());
const char opening_bracket = input[pos];
const char closing_bracket = (
opening_bracket == '[' ? ']' :
opening_bracket == '{' ? '}' :
opening_bracket == '(' ? ')' :
char()
);
PASRE_CHECK(closing_bracket);
PASRE_CHECK(pos < input.size());
while (true) {
const char c = input[pos++];
if (c == closing_bracket)
break;
PASRE_CHECK(pos < input.size());
if (c == ' ')
continue;
result.emplace_back(parse<typename T::value_type>(input, pos));
}
result.shrink_to_fit();
return std::move(result);
}
template<typename T>
T&& parse(const std::string_view& input, size_t&& pos = 0, T&& result = T()) {
return parse<T>(input, pos, std::move(result));
}
#ifdef __PARSE_CHAR_QUOTE__
template<>
char&& parse(const std::string_view& input, size_t& pos, char&& result) {
PASRE_CHECK(pos < input.size());
result = input[pos++];
if(result == __PARSE_CHAR_QUOTE__) {
PASRE_CHECK(pos + 1 < input.size() && input[pos + 1] != __PARSE_CHAR_QUOTE__);
result = input[pos];
pos += 2;
}
return std::move(result);
}
#else
template<>
char&& parse(const std::string_view& input, size_t& pos, char&& result) {
PASRE_CHECK(pos < input.size());
result = input[pos++];
return std::move(result);
}
#endif
#define DECLARE_PASRE_UNSIGNED_INTEGER(IntegerType) \
template<> \
IntegerType&& parse(const std::string_view& input, size_t& pos, IntegerType&& result) { \
skip_whitespaces(input, pos); \
while (true) { \
PASRE_CHECK(pos < input.size()); \
if(!std::isdigit(input[pos])) \
break; \
result = result * 10 + (input[pos++] - '0'); \
} \
return std::move(result); \
}
DECLARE_PASRE_UNSIGNED_INTEGER(unsigned short);
DECLARE_PASRE_UNSIGNED_INTEGER(unsigned int);
DECLARE_PASRE_UNSIGNED_INTEGER(unsigned long);
DECLARE_PASRE_UNSIGNED_INTEGER(unsigned long long);
#ifdef __PARSE_INT128__
DECLARE_PASRE_UNSIGNED_INTEGER(unsigned __int128);
#endif
#define DECLARE_PASRE_SIGNED_INTEGER(IntegerType) \
template<> \
IntegerType&& parse(const std::string_view& input, size_t& pos, IntegerType&& result) { \
skip_whitespaces(input, pos); \
bool neg = input[pos] == '-'; \
pos += neg || input[pos] == '+'; \
auto temp = parse<unsigned IntegerType>(input, pos, result); \
result = neg ? -temp : temp; \
return std::move(result); \
}
DECLARE_PASRE_SIGNED_INTEGER(short);
DECLARE_PASRE_SIGNED_INTEGER(int);
DECLARE_PASRE_SIGNED_INTEGER(long);
DECLARE_PASRE_SIGNED_INTEGER(long long);
#ifdef __PARSE_INT128__
DECLARE_PASRE_SIGNED_INTEGER(__int128);
#endif
#ifdef __PARSE_STRING_DELIMITER__
template<>
std::string&& parse(const std::string_view& input, size_t& pos, std::string&& result) {
skip_whitespaces(input, pos);
while (true) {
PASRE_CHECK(pos < input.size());
if (std::find(
std::begin(__PARSE_STRING_DELIMITER__),
std::end(__PARSE_STRING_DELIMITER__),
input[pos]) != std::end(__PARSE_STRING_DELIMITER__)
)
break;
result += input[pos++];
}
return move(result);
}
#else
template<>
std::string&& parse(const std::string_view& input, size_t& pos, std::string&& result) {
skip_whitespaces(input, pos);
PASRE_CHECK(input[pos] == '"');
pos += 1;
while (true) {
PASRE_CHECK(pos < input.size());
if (input[pos] == '\'' || input[pos] == '"')
break;
result += input[pos++];
}
pos++;
return std::move(result);
}
#endif
// Shortcuts //
#define DECLARE_PARSE_SHORTCUT(FnName, Type) \
Type FnName(const std::string_view& input) { \
return parse<Type>(input); \
}
DECLARE_PARSE_SHORTCUT(vs, std::vector<std::string>);
DECLARE_PARSE_SHORTCUT(vvs, std::vector<std::vector<std::string>>);
DECLARE_PARSE_SHORTCUT(vc, std::vector<char>);
DECLARE_PARSE_SHORTCUT(vvc, std::vector<std::vector<char>>);
DECLARE_PARSE_SHORTCUT(vi, std::vector<int>);
DECLARE_PARSE_SHORTCUT(vvi, std::vector<std::vector<int>>);
DECLARE_PARSE_SHORTCUT(vl, std::vector<long long>);
DECLARE_PARSE_SHORTCUT(vvl, std::vector<std::vector<long long>>);
#ifdef __PARSE_INT128__
DECLARE_PARSE_SHORTCUT(vi128, std::vector<__int128>);
DECLARE_PARSE_SHORTCUT(vvi128, std::vector<std::vector<__int128>>);
#endif
// DECLARE_PARSE_SHORTCUT(vf, std::vector<float>);
// DECLARE_PARSE_SHORTCUT(vvf, std::vector<std::vector<float>>);
// DECLARE_PARSE_SHORTCUT(vd, std::vector<double>);
// DECLARE_PARSE_SHORTCUT(vvd, std::vector<std::vector<double>>);
};
// ========== LEETCODE ========== //
using namespace leetcode;
using namespace std;
// Solution //
class Solution {
public:
vector<vector<int>> matrixRankTransform(vector<vector<int>>& A) {
using Id=short;
const int N=A.size(), M=A[0].size();
vector<tuple<int, Id, Id>> B(N*M);
for(int i=0, k=0; i<N; i++)
for(int j=0; j<M; j++)
B[k++]={A[i][j], i, j};
sort(B.begin(), B.end());
vector<int> X(N), Y(M);
vector<pair<short, short>> Q(N*M);
vector<Id> Xp(N, -1), Yp(M, -1);
vector<vector<array<Id, 4>>> G(N, vector<array<Id, 4>>(M));
for(int l=0, r=0, s=0, e=0; l<N*M; l=r) {
for(; r<N*M && get<0>(B[l])==get<0>(B[r]); r++) {
auto[x,i,j]=B[r];
Id &px=Xp[i], &py=Yp[j];
G[i][j]={px, py, -1, -1};
if(~px) G[i][px][2]=j;
if(~py) G[py][j][3]=i;
px=j, py=i;
A[i][j]=~max(X[i], Y[j]);
}
for(; l<r; l++) {
auto[x,i,j]=B[l];
if(A[i][j]>0) continue;
int m=-A[i][j];
Q[e++]={i, j};
A[i][j]=0;
int t=s;
while(s<e) {
auto[i2,j2]=Q[s++];
for(int k=0; k<4; k++)
if(int y=i2, x=j2; ~((k&1 ? y : x)=G[i2][j2][k]) && A[y][x]<0) {
m=max(m, -A[y][x]);
Q[e++]={y, x};
A[y][x]=0;
}
}
while(t<e) {
auto[y,x]=Q[t++];
X[y]=Y[x]=A[y][x]=m;
Xp[y]=Yp[x]=-1;
}
}
}
return move(A);
}
};
// Checker
template<typename T, typename T1, typename... Ts>
bool test(T ans, T1 arg, Ts... args) {
Solution sol;
auto _arg = arg;
auto res = sol.matrixRankTransform(arg, args...);
// std::sort(ans.begin(), ans.end());
// std::sort(res.begin(), res.end());
bool ok = ans == res;
if(ok) {
std::cout << "✅ ";
} else {
std::cout << "❌ ";
}
std::cout << std::forward<T1>(_arg);
((std::cout << ", " << std::forward<Ts>(args)), ...);
std::cout << std::endl;
if(!ok) {
std::cout << "Output: " << res << std::endl;
std::cout << "Answer: " << ans << std::endl;
}
std::cout << std::endl;
return ok;
}
// Tests
// Usage: T(answer, args);
#define T(...) test(__VA_ARGS__)
int main() {
T(vvi("[[1,2],[2,3]]"), vvi("[[1,2],[3,4]]"));
T(vvi("[[1,1],[1,1]]"), vvi("[[7,7],[7,7]]"));
T(vvi("[[4,2,3],[1,3,4],[5,1,6],[1,3,4]]"), vvi("[[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]"));
T(vvi("[[5,1,4],[1,2,3],[6,3,1]]"), vvi("[[7,3,6],[1,4,5],[9,8,2]]"));
T(vvi("[[2,1,4,6],[2,6,5,4],[5,2,4,3],[4,3,1,5]]"), vvi("[[-37,-50,-3,44],[-37,46,13,-32],[47,-42,-3,-40],[-17,-22,-39,24]]"));
T(vvi("[[14,4,5,3,25,2,21,1,14,24,15,29],[21,28,26,3,14,20,1,29,17,4,10,9],[19,16,27,23,28,10,5,22,15,20,17,18],[17,27,25,5,15,19,21,20,16,23,18,22],[1,27,2,28,26,4,3,10,8,21,5,10],[9,6,10,23,4,2,7,21,16,3,5,23],[13,12,27,4,13,23,22,5,16,28,11,5],[8,7,13,24,5,22,23,21,25,15,12,9],[13,29,24,23,2,8,4,9,7,14,6,25],[28,22,27,10,1,22,27,23,9,2,30,29],[28,1,5,8,26,23,30,29,7,3,17,2],[14,22,16,6,26,9,1,15,14,10,1,27]]"), vvi("[[-5,-42,-39,-44,31,-46,13,-48,-5,30,1,48],[31,42,33,-44,-5,14,-47,48,7,-34,-19,-20],[11,2,37,24,39,-6,-27,20,-1,14,5,8],[7,38,29,-28,-1,10,13,12,3,26,9,16],[-49,38,-47,40,35,-42,-43,-8,-21,22,-39,-8],[-17,-38,-15,24,-41,-46,-19,16,3,-42,-39,24],[-9,-14,37,-40,-9,26,17,-28,3,38,-15,-28],[-21,-34,1,36,-37,18,25,16,39,6,-3,-20],[-9,46,25,24,-45,-26,-39,-16,-29,-2,-35,28],[43,18,37,4,-49,18,37,24,-9,-46,49,48],[43,-46,-39,-8,35,26,49,48,-29,-42,5,-44],[-5,18,9,-20,35,-18,-47,-4,-5,-14,-47,44]]"));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment