Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- string gen(int length) {
- srand(time(nullptr));
- string result;
- for (int i = 0; i < length; ++i) {
- result.push_back('a' + rand() % 26);
- }
- return result;
- }
- vector<pair<int, int>> solve(const string& s) {
- string sorted = s;
- sort(sorted.begin(), sorted.end());
- vector<pair<int, int>> result;
- for (int i = 0; i < s.length() - 1; ++i) {
- if (sorted[i] != s[i]) {
- unsigned int pos = sorted.find(s[i], i + 1);
- if (pos == string::npos) {
- cout << "input: " << s << endl;
- exit(EXIT_FAILURE);
- }
- if (sorted[i] > s[i]) {
- result.emplace_back(i, pos);
- } else {
- result.emplace_back(pos, i);
- }
- swap(sorted[i], sorted[pos]);
- }
- }
- return result;
- };
- bool apply(const string& s, const vector<pair<int, int>>& sol) {
- if (sol.size() > 10000) {
- return false;
- }
- string tmp = s;
- sort(tmp.begin(), tmp.end());
- for (const auto& move : sol) {
- int a = move.first;
- int b = move.second;
- if (tmp[a] > tmp[b]) {
- swap(tmp[a], tmp[b]);
- }
- }
- return tmp == s;
- }
- ostream& operator << (ostream& out, const vector<pair<int, int>>& v) {
- for (const auto& p : v) {
- out << "(" << p.first << "," << p.second << ") ";
- }
- return out;
- }
- int main() {
- int tests = 1000;
- int passed = 0;
- int failed = 0;
- for (int i = 0; i < tests; ++i) {
- string input = gen(1000);
- auto sol = solve(input);
- if (!apply(input, sol)) {
- cout << "Wrong for " << input << endl;
- failed++;
- } else {
- passed++;
- }
- }
- cout << "Passed: " << passed << " " << "Failed: " << failed << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement