Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #pragma comment(linker, "/STACK:167772160000")
- #include <iostream>
- #include <iomanip>
- #include <fstream>
- #include <stdio.h>
- #include <cstdio>
- #include <stdlib.h>
- #include <cstdlib>
- #include <algorithm>
- #include <cstring>
- #include <string>
- #include <vector>
- #include <list>
- #include <stack>
- #include <climits>
- #include <set>
- #include <bitset>
- #include <math.h>
- #include <queue>
- #include <map>
- #include <sstream>
- #include <functional>
- #include <assert.h>
- #include <unordered_map>
- #include <unordered_set>
- #include <complex>
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef std::pair<int, int> pii;
- typedef std::pair<double, double> pdd;
- template <typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
- template <typename T> using max_heap = std::priority_queue<T, std::vector<T>, std::less<T>>;
- #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL);
- #define TESTS(t) int NUMBER_OF_TESTS; cin >> NUMBER_OF_TESTS; for(int t = 1; t <= NUMBER_OF_TESTS; t++)
- #define FOR(i, start, end) for(int i = (start); i < (end); i++)
- #define ROF(i, start, end) for(int i = (start); i >= (end); i--)
- #define all(x) (x).begin(), (x).end()
- //#define endl "\n"
- #define PI (asin(1)*2)
- #define OO ((1LL<<31)-1)
- #define eps 1e-12
- #define in(a, b) ((b).find(a) != (b).end())
- #define mp(a, b) make_pair((a), (b))
- #define sgn(a) ((a) > eps ? 1 : ((a) < -eps ? -1 : 0))
- #define cl1(x) ((x)&((x)-1)) // clear lowest 1 bit
- #define cl0(x) ((x)|((x)+1)) // clear lowest 0 bit
- #define ct1(x) ((x)&((x)+1)) // clear all trailing 1 bits
- #define pb push_back
- #define MOD 1000000007
- #define MAX_N 1000000
- using namespace std;
- string signs = "";
- set<char> letters;
- int din[50];
- int dout[50];
- bool connected[50][50];
- vector<int> neigh[50];
- bool isGood(const string& s) {
- for (auto c : letters) {
- din[c - 'a'] = dout[c - 'a'] = 0;
- neigh[c - 'a'].clear();
- for (auto cc : letters) connected[c - 'a'][cc - 'a'] = false;
- }
- FOR(i, 0, signs.length()) {
- int bef = s[i] - 'a';
- int aft = s[i + 1] - 'a';
- if (signs[i] == '<') {
- if (!connected[aft][bef]) {
- din[bef]++;
- dout[aft]++;
- neigh[aft].pb(bef);
- connected[aft][bef] = true;
- }
- }
- else if (signs[i] == '>') {
- if (!connected[bef][aft]) {
- dout[bef]++;
- din[aft]++;
- neigh[bef].pb(aft);
- connected[bef][aft] = true;
- }
- }
- }
- stack<int> S;
- for (auto c : letters) {
- if (din[c-'a'] == 0) {
- S.push(c-'a');
- }
- }
- int cnt = 0;
- while (!S.empty()) {
- if (S.size() > 1) {
- return false;
- }
- int top = S.top(); S.pop();
- for (auto n : neigh[top]) {
- din[n]--;
- if (din[n] == 0) S.push(n);
- }
- cnt++;
- }
- return cnt == letters.size();
- }
- void buildSigns(const string& s, int idx) {
- if (idx == s.length() - 1) {
- // check
- if (isGood(s)) {
- FOR(i, 0, signs.length()) {
- cout << s[i] << " " << signs[i] << " ";
- }
- cout << s[s.length() - 1] << endl;
- exit(0);
- }
- return;
- }
- if (s[idx] == s[idx + 1]) {
- signs[idx] = '=';
- buildSigns(s, idx + 1);
- return;
- }
- int bef = s[idx] - 'a';
- int aft = s[idx + 1] - 'a';
- if (!connected[aft][bef]) {
- signs[idx] = '>';
- connected[bef][aft] = true;
- buildSigns(s, idx + 1);
- connected[bef][aft] = false;
- }
- if (!connected[bef][aft]) {
- connected[aft][bef] = true;
- signs[idx] = '<';
- buildSigns(s, idx + 1);
- connected[aft][bef] = false;
- }
- }
- int main()
- {
- FAST_IO
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- string s;
- cin >> s;
- for (char c : s) {
- signs += " ";
- letters.insert(c);
- }
- signs = signs.substr(0, signs.length() - 1);
- buildSigns(s, 0);
- cout << "Impossible" << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement