SRM 300 Div2 Medium 500 points

Dating.cpp

#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cassert>
#include <iterator>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long lint;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, x, n) for(int i=x;i<n;i++)
#define MSG(s) cout << #s << " " << endl;
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }


class Dating
{
public:
	string dates(string circle, int k)
	{
		int S = circle.size();
		priority_queue<char, vector<char>, greater<char> > M, W;
		map<char, bool> used;

		for(int i = 0; i < S; i++){
			(isupper(circle[i]) ? M : W).push(circle[i]);
		}

		string ans = "";

		for(int idx = 0; !(M.empty() || W.empty()); ){
			while(!M.empty() && used[M.top()]) M.pop();
			while(!W.empty() && used[W.top()]) W.pop();

			if(M.empty() || W.empty()) break;			

			for(int i = (ans == ""); i < k; i += !used[circle[(idx += 1) %= S]]);

			char o = (isupper(circle[idx]) ? W : M).top();

			ans += string(1, circle[idx]) + string(1, o) + " ";

			used[circle[idx]] = used[o] = true;
		}

		return ans.substr(0, ans.size()-1);
	}
};

// BEGIN CUT HERE
namespace moj_harness {
	int run_test_case(int);
	void run_test(int casenum = -1, bool quiet = false) {
		if (casenum != -1) {
			if (run_test_case(casenum) == -1 && !quiet) {
				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
			}
			return;
		}
		
		int correct = 0, total = 0;
		for (int i=0;; ++i) {
			int x = run_test_case(i);
			if (x == -1) {
				if (i >= 100) break;
				continue;
			}
			correct += x;
			++total;
		}
		
		if (total == 0) {
			cerr << "No test cases run." << endl;
		} else if (correct < total) {
			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
		} else {
			cerr << "All " << total << " tests passed!" << endl;
		}
	}
	
	int verify_case(int casenum, const string &expected, const string &received, clock_t elapsed) { 
		cerr << "Example " << casenum << "... "; 
		
		string verdict;
		vector<string> info;
		char buf[100];
		
		if (elapsed > CLOCKS_PER_SEC / 200) {
			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
			info.push_back(buf);
		}
		
		if (expected == received) {
			verdict = "PASSED";
		} else {
			verdict = "FAILED";
		}
		
		cerr << verdict;
		if (!info.empty()) {
			cerr << " (";
			for (int i=0; i<(int)info.size(); ++i) {
				if (i > 0) cerr << ", ";
				cerr << info[i];
			}
			cerr << ")";
		}
		cerr << endl;
		
		if (verdict == "FAILED") {
			cerr << "    Expected: \"" << expected << "\"" << endl; 
			cerr << "    Received: \"" << received << "\"" << endl; 
		}
		
		return verdict == "PASSED";
	}

	int run_test_case(int casenum__) {
		switch (casenum__) {
		case 0: {
			string circle             = "abXCd";
			int k                     = 2;
			string expected__         = "bC dX";

			clock_t start__           = clock();
			string received__         = Dating().dates(circle, k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}
		case 1: {
			string circle             = "abXCd";
			int k                     = 8;
			string expected__         = "Xa dC";

			clock_t start__           = clock();
			string received__         = Dating().dates(circle, k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}
		case 2: {
			string circle             = "HGFhgfz";
			int k                     = 1;
			string expected__         = "Hf Gg Fh";

			clock_t start__           = clock();
			string received__         = Dating().dates(circle, k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}

		// custom cases

/*      case 3: {
			string circle             = ;
			int k                     = ;
			string expected__         = ;

			clock_t start__           = clock();
			string received__         = Dating().dates(circle, k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}*/
/*      case 4: {
			string circle             = ;
			int k                     = ;
			string expected__         = ;

			clock_t start__           = clock();
			string received__         = Dating().dates(circle, k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}*/
/*      case 5: {
			string circle             = ;
			int k                     = ;
			string expected__         = ;

			clock_t start__           = clock();
			string received__         = Dating().dates(circle, k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}*/
		default:
			return -1;
		}
	}
}


int main(int argc, char *argv[]) {
	if (argc == 1) {
		moj_harness::run_test();
	} else {
		for (int i=1; i<argc; ++i)
			moj_harness::run_test(atoi(argv[i]));
	}
}
// END CUT HERE