library

Some useful algorithms for competitive programming

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  63. 63
  64. 64
  65. 65
  66. 66
  67. 67
  68. 68
  69. 69
  70. 70
  71. 71
  72. 72
  73. 73
  74. 74
  75. 75
  76. 76
  77. 77
  78. 78
  79. 79
  80. 80
  81. 81
  82. 82
  83. 83
  84. 84
  85. 85
  86. 86
  87. 87
  88. 88
  89. 89
  90. 90
  91. 91
  92. 92
  93. 93
  94. 94
  95. 95
  96. 96
  97. 97
  98. 98
  99. 99
  100. 100
  101. 101
  102. 102
  103. 103
  104. 104
  105. 105
  106. 106
  107. 107
  108. 108
  109. 109
  110. 110
  111. 111
  112. 112
  113. 113
# use this to grade your program given the input and output files

IN="$1/#.in"
OUT="$1/#.out"

TL=2
CPP="g++ -o .vscode/$1 -O2 -w -lm" # C++, -w = suppress warnings

red='\x1B[0;31m'
RED='\x1B[1;31m'
GREEN='\x1B[1;32m'
green='\x1B[0;32m'
blue='\x1B[0;34m'
BLUE='\x1B[1;34m'
cyan='\x1B[0;36m'
CYAN='\x1B[1;36m'
NC='\x1B[0m' # No Color

rm -f .overview .compiler_report .time_info .$1.out
trap "{ rm -f .overview .compiler_report .time_info .$1.out; }" SIGINT SIGTERM EXIT


if [ $# -ne 1 ]
then
	echo "Usage: $0 source_code"
	echo "   e.g. $0 test.cpp"
	echo "   use the above to grade file test.cpp"
	exit 2
fi

# Language detection
LANG=`echo $1.cpp | awk -F . '{print $NF}'`
if [ "$LANG" == "cpp" ]
then
	COMPILER="$CPP $1.cpp 2> .compiler_report" # C++
fi

# Compilation
echo -e " ${CYAN}* Compiling source code${NC}";
echo "$COMPILER" | sh
if [ $? -ne 0 ]
then
	echo -e " ${RED}X Compilation Error${NC}";
	cat .compiler_report;
	exit 1;
fi

echo -e " ${GREEN}* Successful compilation!${NC}";
echo

ulimit -t $TL;

rm -rf .overview;
CORRECT=0
MAX_N=50

for (( i=1; i<=$MAX_N; i++))
do
	TEST_CASE_IN=`echo $IN | sed "s/#/$i/g"`
	TEST_CASE_OUT=`echo $OUT | sed "s/#/$i/g"`

	# If i-th test case doesn't exist then stop here.
	if [ ! -e $TEST_CASE_IN ]
	then
		break
	fi
	echo -e "${BLUE}Test case $i:${NC}";

	time -p (./.vscode/$1 1 < $TEST_CASE_IN > .$1.out) 2> .time_info;

	EX_CODE=$?;
	if [ $EX_CODE -eq 152 ]
	then
		echo -e " ${RED}X TLE: Time Limit Exceeded${NC}";
		echo -n "T" >> .overview;
	elif [ $EX_CODE -ne 0 ]
	then
		echo -e " ${RED}X RE: Runtime Error${NC}";
		echo -n "E" >> .overview;
	else
		PROG_TIME=`cat .time_info | grep real | cut -d" " -f2`;
		diff --strip-trailing-cr .$1.out $TEST_CASE_OUT > /dev/null
		if [ $? -eq 0 ]
		then
			echo -e " ${GREEN}* OK${NC} [$PROG_TIME]"
			echo -n "*" >> .overview
			CORRECT=`expr $CORRECT + 1`
		else
			echo -e " ${RED}X WA: Wrong Answer${NC} [$PROG_TIME]"
			echo -n "X" >> .overview
		fi
	fi

	echo;
done
N=`expr $i - 1`

echo;

echo >> .overview;
echo -n "Overview: "; cat .overview
if [ $CORRECT -ne $N ]
then
	echo -e "${RED}X${NC}: Wrong Answer, ${RED}T${NC}: Time Limit Exceeded, ${RED}E${NC}: Probably runtime error"
	echo
fi

echo -n "$CORRECT / $N"
if [ $CORRECT -eq $N ]
then
	echo -en "   ${GREEN}AWWW YEAH :D${NC}"
fi
echo