Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.91 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string gen(int length) {
  5.     srand(time(nullptr));
  6.     string result;
  7.     for (int i = 0; i < length; ++i) {
  8.         result.push_back('a' + rand() % 26);
  9.     }
  10.     return result;
  11. }
  12.  
  13. vector<pair<int, int>> solve(const string& s) {
  14.     string sorted = s;
  15.     sort(sorted.begin(), sorted.end());
  16.     vector<pair<int, int>> result;
  17.     for (int i = 0; i < s.length() - 1; ++i) {
  18.         if (sorted[i] != s[i]) {
  19.             unsigned int pos = sorted.find(s[i], i + 1);
  20.             if (pos == string::npos) {
  21.                 cout << "input: " << s << endl;
  22.                 exit(EXIT_FAILURE);
  23.             }
  24.             if (sorted[i] > s[i]) {
  25.                 result.emplace_back(i, pos);
  26.             } else {
  27.                 result.emplace_back(pos, i);
  28.             }
  29.             swap(sorted[i], sorted[pos]);
  30.         }
  31.     }
  32.     return result;
  33. };
  34.  
  35. bool apply(const string& s, const vector<pair<int, int>>& sol) {
  36.     if (sol.size() > 10000) {
  37.         return false;
  38.     }
  39.     string tmp = s;
  40.     sort(tmp.begin(), tmp.end());
  41.     for (const auto& move : sol) {
  42.         int a = move.first;
  43.         int b = move.second;
  44.         if (tmp[a] > tmp[b]) {
  45.             swap(tmp[a], tmp[b]);
  46.         }
  47.     }
  48.     return tmp == s;
  49. }
  50.  
  51. ostream& operator << (ostream& out, const vector<pair<int, int>>& v) {
  52.     for (const auto& p : v) {
  53.         out << "(" << p.first << "," << p.second << ") ";
  54.     }
  55.     return out;
  56. }
  57.  
  58. int main() {
  59.     int tests = 1000;
  60.     int passed = 0;
  61.     int failed = 0;
  62.     for (int i = 0; i < tests; ++i) {
  63.         string input = gen(1000);
  64.         auto sol = solve(input);
  65.         if (!apply(input, sol)) {
  66.             cout << "Wrong for " << input << endl;
  67.             failed++;
  68.         } else {
  69.             passed++;
  70.         }
  71.     }
  72.     cout << "Passed: " << passed << " " << "Failed: " << failed << endl;
  73.     return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement