#include #include #include #include #include #include #include #include /* Randomly searches for a valid permutation. What are the changes of finding a solution? No idea, hopefully pretty low on some test cases! We use a fixed seed, so that the solution is deterministic. BUT we use a time bound, making it non-deterministic. */ using namespace std; // Since the checking is fast, we can probably get away with // setting the time_limit to the exact limit... const long double time_limit = 0.85; int main(){ int n; cin >> n; // adjacency matrix vector> beats(n, vector(n, false)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { char c; cin >> c; if (c == '1') beats[i][j] = true; } } vector solution(n); iota(solution.begin(), solution.end(), 0); // 0-based function simulate = [&]() { int king = solution[0]; for (int i = 1; i < n; ++i) { int challenger = solution[i]; if (beats[challenger][king]) king = challenger; } return king == 0; // Henk wins }; mt19937 gen; const auto time_bound = chrono::steady_clock::now() + chrono::duration(time_limit); long long tries = 0; do { tries++; shuffle(solution.begin(), solution.end(), gen); if (simulate()) { cout << solution[0]; for (int i = 1; i < n; ++i) { cout << ' ' << solution[i]; } cout << endl; clog << tries << endl; return 0; } } while (chrono::steady_clock::now() < time_bound); // timeout -> impossible cout << "impossible" << endl; clog << tries << endl; }