fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define MP make_pair
  3. #define PB push_back
  4. #define int long long
  5. #define st first
  6. #define nd second
  7. #define rd third
  8. #define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
  9. #define RE(i, n) FOR(i, 1, n)
  10. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  11. #define REP(i, n) for(int i = 0;i <(n); ++i)
  12. #define VAR(v, i) __typeof(i) v=(i)
  13. #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
  14. #define ALL(x) (x).begin(), (x).end()
  15. #define SZ(x) ((int)(x).size())
  16.  
  17. #define make(type, x) type x; cin>>x;
  18. #define make2(type, x, y) type x, y; cin>>x>>y;
  19. #define make3(type, x, y, z) type x, y, z; cin>>x>>y>>z;
  20. #define make4(type, x, y, z, t) type x, y, z, t; cin>>x>>y>>z>>t;
  21. #define next ____next
  22. #define prev ____prev
  23. #define left ____left
  24. #define hash ____hash
  25. using namespace std;
  26. typedef long long ll;
  27. typedef long double LD;
  28. typedef pair<int, int> PII;
  29. typedef pair<ll, ll> PLL;
  30. typedef vector<int> VI;
  31. typedef vector<ll> VLL;
  32. typedef vector<pair<int, int> > VPII;
  33. typedef vector<pair<ll, ll> > VPLL;
  34.  
  35. template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
  36. template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
  37. template<class T1, class T2>
  38. ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
  39. template<class A, class B, class C> struct Triple { A first; B second; C third; };
  40. template<class T> void ResizeVec(T&, vector<int>) {}
  41. template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) {
  42.   vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; }
  43.   for (T& v : vec) { ResizeVec(v, sz); }
  44. }
  45.  
  46. template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
  47. template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
  48.   while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
  49. }
  50. #ifdef LOCAL
  51. #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
  52. #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
  53. #else
  54. #define debug(...) (__VA_ARGS__)
  55. #define debugv(x)
  56. #define cerr if(0)cout
  57. #endif
  58.  
  59. typedef vector<VI> VVI;
  60. class ParenthesesDiv1Hard {
  61. public:
  62.   int depth(string s) {
  63.     int bil = 0;
  64.     int dep = 0;
  65.     for (int i = 0; i < SZ(s); i++) {
  66.       if (s[i] == '(') {
  67.         bil++;
  68.         maxi(dep, bil);
  69.       } else {
  70.         bil--;
  71.       }
  72.     }
  73. /*    if (bil != 0) {
  74.       reutrn*/ 
  75.     //assert(bil == 0);
  76.     return dep;
  77.   }
  78.   int cost(string s) {
  79.     if (s == "") {
  80.       return 0;
  81.     }
  82.     int bil = 0;
  83.     for (int i = 0; i < SZ(s); i++) {
  84.       if (s[i] == '(') {
  85.         bil++;
  86.       } else {
  87.         bil--;
  88.       }
  89.       if (bil == 0 && i < SZ(s) - 1) {
  90.         return cost(s.substr(0, i + 1)) + cost(s.substr(i + 1));
  91.       }
  92.     }
  93.     int d = depth(s);
  94.     debug(s, d);
  95.     return d * d + cost(s.substr(1, SZ(s) - 2));
  96.   }
  97. #undef int
  98.   int minCost(string s) {
  99. #define int long long
  100.  
  101.     string left, right;
  102.     int hei_left = 0, hei_right = 0;
  103.     int min_hei = 0;
  104.     debug(s);
  105.     for (int i = 0; i < SZ(s); i++) {
  106.       if (s[i] == '(') {
  107.         if (hei_right < hei_left) {
  108.           right += '(';
  109.           hei_right++;
  110.         } else {
  111.           left += '(';
  112.           hei_left++;
  113.         }
  114.       } else {
  115.         if (hei_right == hei_left) {
  116.           right += ')';
  117.           hei_right--;
  118.         } else {
  119.           left += ')';
  120.           hei_left--;
  121.         }
  122.       }
  123.       mini(min_hei, hei_right);
  124.     }
  125.     if (min_hei < 0 || hei_left != 0 || hei_right != 0) {
  126.       return {-1};
  127.     }
  128.     debug(left, right);
  129.     int l = cost(left), r = cost(right);
  130.     debug(l, r);
  131.     return l + r;
  132.   //  return cost(left) + cost(right);
  133.  
  134.  
  135.   }
  136.  
  137. };
  138.  
  139. #undef int
  140.  
  141. // BEGIN CUT HERE
  142. #include <cstdio>
  143. #include <ctime>
  144. #include <iostream>
  145. #include <string>
  146. #include <vector>
  147. namespace moj_harness {
  148. 	using std::string;
  149. 	using std::vector;
  150. 	int run_test_case(int);
  151. 	void run_test(int casenum = -1, bool quiet = false) {
  152. 		if (casenum != -1) {
  153. 			if (run_test_case(casenum) == -1 && !quiet) {
  154. 				std::cerr << "Illegal input! Test case " << casenum << " does not exist." << std::endl;
  155. 			}
  156. 			return;
  157. 		}
  158.  
  159. 		int correct = 0, total = 0;
  160. 		for (int i=0;; ++i) {
  161. 			int x = run_test_case(i);
  162. 			if (x == -1) {
  163. 				if (i >= 100) break;
  164. 				continue;
  165. 			}
  166. 			correct += x;
  167. 			++total;
  168. 		}
  169.  
  170. 		if (total == 0) {
  171. 			std::cerr << "No test cases run." << std::endl;
  172. 		} else if (correct < total) {
  173. 			std::cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << std::endl;
  174. 		} else {
  175. 			std::cerr << "All " << total << " tests passed!" << std::endl;
  176. 		}
  177. 	}
  178.  
  179. 	int verify_case(int casenum, const int &expected, const int &received, std::clock_t elapsed) { 
  180. 		std::cerr << "Example " << casenum << "... "; 
  181.  
  182. 		string verdict;
  183. 		vector<string> info;
  184. 		char buf[100];
  185.  
  186. 		if (elapsed > CLOCKS_PER_SEC / 200) {
  187. 			std::sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
  188. 			info.push_back(buf);
  189. 		}
  190.  
  191. 		if (expected == received) {
  192. 			verdict = "PASSED";
  193. 		} else {
  194. 			verdict = "FAILED";
  195. 		}
  196.  
  197. 		std::cerr << verdict;
  198. 		if (!info.empty()) {
  199. 			std::cerr << " (";
  200. 			for (size_t i=0; i<info.size(); ++i) {
  201. 				if (i > 0) std::cerr << ", ";
  202. 				std::cerr << info[i];
  203. 			}
  204. 			std::cerr << ")";
  205. 		}
  206. 		std::cerr << std::endl;
  207.  
  208. 		if (verdict == "FAILED") {
  209. 			std::cerr << "    Expected: " << expected << std::endl; 
  210. 			std::cerr << "    Received: " << received << std::endl; 
  211. 		}
  212.  
  213. 		return verdict == "PASSED";
  214. 	}
  215.  
  216. 	int run_test_case(int casenum__) {
  217. 		switch (casenum__) {
  218. 		case 0: {
  219. 			string s                  = "(())";
  220. 			int expected__            = 2;
  221.  
  222. 			std::clock_t start__      = std::clock();
  223. 			int received__            = ParenthesesDiv1Hard().minCost(s);
  224. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  225. 		}
  226. 		case 1: {
  227. 			string s                  = "((())())(()()())";
  228. 			int expected__            = 11;
  229.  
  230. 			std::clock_t start__      = std::clock();
  231. 			int received__            = ParenthesesDiv1Hard().minCost(s);
  232. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  233. 		}
  234. 		case 2: {
  235. 			string s                  = "())(()";
  236. 			int expected__            = -1;
  237.  
  238. 			std::clock_t start__      = std::clock();
  239. 			int received__            = ParenthesesDiv1Hard().minCost(s);
  240. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  241. 		}
  242. 		case 3: {
  243. 			string s                  = "(((((((((())))))))))";
  244. 			int expected__            = 110;
  245.  
  246. 			std::clock_t start__      = std::clock();
  247. 			int received__            = ParenthesesDiv1Hard().minCost(s);
  248. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  249. 		}
  250. 		case 4: {
  251. 			string s                  = "()";
  252. 			int expected__            = 1;
  253.  
  254. 			std::clock_t start__      = std::clock();
  255. 			int received__            = ParenthesesDiv1Hard().minCost(s);
  256. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  257. 		}
  258. 		case 5: {
  259. 			string s                  = "(((())()()()((((()))))(((())))()()()))(()(()))";
  260. 			int expected__            = 69;
  261.  
  262. 			std::clock_t start__      = std::clock();
  263. 			int received__            = ParenthesesDiv1Hard().minCost(s);
  264. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  265. 		}
  266.  
  267. 		// custom cases
  268.  
  269. /*      case 6: {
  270. 			string s                  = ;
  271. 			int expected__            = ;
  272.  
  273. 			std::clock_t start__      = std::clock();
  274. 			int received__            = ParenthesesDiv1Hard().minCost(s);
  275. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  276. 		}*/
  277. /*      case 7: {
  278. 			string s                  = ;
  279. 			int expected__            = ;
  280.  
  281. 			std::clock_t start__      = std::clock();
  282. 			int received__            = ParenthesesDiv1Hard().minCost(s);
  283. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  284. 		}*/
  285. /*      case 8: {
  286. 			string s                  = ;
  287. 			int expected__            = ;
  288.  
  289. 			std::clock_t start__      = std::clock();
  290. 			int received__            = ParenthesesDiv1Hard().minCost(s);
  291. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  292. 		}*/
  293. 		default:
  294. 			return -1;
  295. 		}
  296. 	}
  297. }
  298.  
  299.  
  300. #include <cstdlib>
  301. int main(int argc, char *argv[]) {
  302. 	if (argc == 1) {
  303. 		moj_harness::run_test();
  304. 	} else {
  305. 		for (int i=1; i<argc; ++i)
  306. 			moj_harness::run_test(std::atoi(argv[i]));
  307. 	}
  308. }
  309. // END CUT HERE
  310.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function 'void moj_harness::run_test(int, bool)':
prog.cpp:56:14: error: expected unqualified-id before 'if'
 #define cerr if(0)cout
              ^
prog.cpp:154:10: note: in expansion of macro 'cerr'
     std::cerr << "Illegal input! Test case " << casenum << " does not exist." << std::endl;
          ^
prog.cpp:56:14: error: expected unqualified-id before 'if'
 #define cerr if(0)cout
              ^
prog.cpp:171:9: note: in expansion of macro 'cerr'
    std::cerr << "No test cases run." << std::endl;
         ^
prog.cpp:56:14: error: expected unqualified-id before 'if'
 #define cerr if(0)cout
              ^
prog.cpp:173:9: note: in expansion of macro 'cerr'
    std::cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << std::endl;
         ^
prog.cpp:56:14: error: expected unqualified-id before 'if'
 #define cerr if(0)cout
              ^
prog.cpp:175:9: note: in expansion of macro 'cerr'
    std::cerr << "All " << total << " tests passed!" << std::endl;
         ^
prog.cpp: In function 'int moj_harness::verify_case(int, const int&, const int&, clock_t)':
prog.cpp:56:14: error: expected unqualified-id before 'if'
 #define cerr if(0)cout
              ^
prog.cpp:180:8: note: in expansion of macro 'cerr'
   std::cerr << "Example " << casenum << "... "; 
        ^
prog.cpp:56:14: error: expected unqualified-id before 'if'
 #define cerr if(0)cout
              ^
prog.cpp:197:8: note: in expansion of macro 'cerr'
   std::cerr << verdict;
        ^
prog.cpp:56:14: error: expected unqualified-id before 'if'
 #define cerr if(0)cout
              ^
prog.cpp:199:9: note: in expansion of macro 'cerr'
    std::cerr << " (";
         ^
prog.cpp:56:14: error: expected unqualified-id before 'if'
 #define cerr if(0)cout
              ^
prog.cpp:201:21: note: in expansion of macro 'cerr'
     if (i > 0) std::cerr << ", ";
                     ^
prog.cpp:56:14: error: expected unqualified-id before 'if'
 #define cerr if(0)cout
              ^
prog.cpp:202:10: note: in expansion of macro 'cerr'
     std::cerr << info[i];
          ^
prog.cpp:56:14: error: expected unqualified-id before 'if'
 #define cerr if(0)cout
              ^
prog.cpp:204:9: note: in expansion of macro 'cerr'
    std::cerr << ")";
         ^
prog.cpp:56:14: error: expected unqualified-id before 'if'
 #define cerr if(0)cout
              ^
prog.cpp:206:8: note: in expansion of macro 'cerr'
   std::cerr << std::endl;
        ^
prog.cpp:56:14: error: expected unqualified-id before 'if'
 #define cerr if(0)cout
              ^
prog.cpp:209:9: note: in expansion of macro 'cerr'
    std::cerr << "    Expected: " << expected << std::endl; 
         ^
prog.cpp:56:14: error: expected unqualified-id before 'if'
 #define cerr if(0)cout
              ^
prog.cpp:210:9: note: in expansion of macro 'cerr'
    std::cerr << "    Received: " << received << std::endl; 
         ^
stdout
copy 
Standard output is empty
https://ideone.com/JgVmI7
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!