/** * @file example_sort.cpp * @brief Solution for the ICPC "Example Sort" problem. * * This program sorts a given word based on a custom set of ordering rules. * The core idea is to represent the ordering rules as a directed graph, * where an edge from character 'a' to 'b' means 'a' must come before 'b'. * * The overall algorithm is as follows: * 1. Build a graph representing the direct relationships given by the n rules. * We use an adjacency matrix for this, where adj[i][j] = true means * character('a'+i) must come before character('a'+j). * * 2. Compute the transitive closure of this graph using the Floyd-Warshall * algorithm. This finds all implied relationships (e.g., if a < b and * b < c, then a < c). * * 3. After finding all relationships, check for contradictions (cycles). A * cycle exists if the rules imply a character must come before itself * (e.g., a < a). This is detected by checking the diagonal of the * adjacency matrix (adj[i][i]). If a cycle is found, sorting is impossible. * * 4. If no cycles exist, sort the input word using a custom comparison * function. This function consults the computed adjacency matrix to decide * the order of any two characters. * * 5. If the rules do not specify an order between two characters, a tie-breaker * is needed for a stable sort. We use standard alphabetical order for this. * The problem statement allows for any valid sorted output if multiple exist, * and this approach produces one such valid output. */ #include #include #include #include #include // Adjacency matrix to store ordering rules for 26 lowercase letters. // adj[i][j] == true means ('a' + i) < ('a' + j). bool adj[26][26]; /** * @brief Custom comparison function for sorting characters. * @param c1 The first character. * @param c2 The second character. * @return True if c1 should come before c2, false otherwise. */ bool compareChars(char c1, char c2) { int u = c1 - 'a'; int v = c2 - 'a'; // Case 1: An explicit or implied rule c1 < c2 exists. if (adj[u][v]) { return true; } // Case 2: An explicit or implied rule c2 < c1 exists. if (adj[v][u]) { return false; } // Case 3: No rule defines the order. Tie-break with alphabetical order. // This ensures a consistent, total ordering for the sort function. return c1 < c2; } int main() { // Use fast I/O std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); // Initialize the adjacency matrix to false (no rules yet). for (int i = 0; i < 26; ++i) { for (int j = 0; j < 26; ++j) { adj[i][j] = false; } } int n; std::cin >> n; std::string line; // Consume the rest of the line after reading n, to prepare for getline. std::getline(std::cin, line); // Step 1: Parse the n rules and populate the adjacency matrix. for (int k = 0; k < n; ++k) { std::getline(std::cin, line); std::stringstream ss(line); char c1, op, c2; ss >> c1 >> op >> c2; int u = c1 - 'a'; int v = c2 - 'a'; if (op == '<') { adj[u][v] = true; } else { // op == '>' adj[v][u] = true; } } // Step 2: Compute transitive closure using Floyd-Warshall algorithm. // This finds all indirect relationships. for (int k = 0; k < 26; ++k) { for (int i = 0; i < 26; ++i) { for (int j = 0; j < 26; ++j) { adj[i][j] = adj[i][j] || (adj[i][k] && adj[k][j]); } } } // Step 3: Check for cycles. A cycle means a character must be < itself. for (int i = 0; i < 26; ++i) { if (adj[i][i]) { std::cout << "IMPOSSIBLE\n"; return 0; } } std::string s; std::cin >> s; // Step 4: Sort the string using our custom comparator. std::sort(s.begin(), s.end(), compareChars); std::cout << s << "\n"; return 0; }