Created
February 2, 2012 22:38
-
-
Save chrisirhc/1726244 to your computer and use it in GitHub Desktop.
Gild Puzzle 320: Gymnast Tower
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstdio> | |
#include <algorithm> | |
#include <vector> | |
#include <set> | |
using namespace std; | |
struct comp { | |
bool operator() (const pair <int, int> i, const pair <int, int> j) const | |
{ return (i.first<j.first); } | |
} compobj; | |
struct comp2 { | |
bool operator() (const pair <int, int> i, const pair <int, int> j) const | |
{ return (i.second<j.second); } | |
} comp2obj; | |
set < pair<int, int> , comp > gymnast; | |
set < pair<int, int> > checks; | |
int main(int argc, char** argv) { | |
FILE * pFile = fopen (argv[1], "r"); | |
int a, b; | |
while (fscanf(pFile, "(%d, %d) ", &a, &b) == 2) { | |
gymnast.insert(make_pair(a, b)); | |
} | |
set< pair<int, int> >::iterator it = gymnast.begin(); | |
checks.insert(make_pair(it->second, 0)); | |
it++; | |
// For each one in the topological order | |
for (; it != gymnast.end(); it++) { | |
// Look back in the edge list | |
set <pair<int, int> >::iterator upperbound = checks.upper_bound(make_pair(it->second, 0)); | |
checks.insert(make_pair(it->second, upperbound != checks.begin() ? | |
(max_element(checks.begin(), upperbound, comp2obj)->second + 1) : 0 | |
)); | |
} | |
printf("%d\n", max_element(checks.begin(), checks.end(), comp2obj)->second + 1); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment