Advertisement
anon20016

Untitled

Nov 22nd, 2019
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.29 KB | None | 0 0
  1. #define _CRT_SECURE_NO_DEPRECATE
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <string>
  6. #include <map>
  7. #include <set>
  8. #include <algorithm>
  9.  
  10. #define ull unsigned long long
  11. #define ll long long
  12.  
  13. using namespace std;
  14.  
  15. const int N = 1001;
  16. const ll INF = 1000ll * 1000 * 1000;
  17.  
  18. //ll a[N];
  19. pair<int, int> d[N];
  20. int p[N];
  21.  
  22. int dx[3] = { 2, 3, 6 };
  23.  
  24. int main() {
  25.     //freopen("input.txt", "r", stdin);
  26.     //freopen("output.txt", "w", stdout);
  27.     int n;
  28.     cin >> n;
  29.     string s;
  30.     cin >> s;
  31.     d[0] = { 0, 0 };
  32.     for (int i = 1; i < n; i++) {
  33.         d[i] = { INF, 0 };
  34.  
  35.         if (s[i] == 'w')
  36.             continue;
  37.         for (int j = 0; j < 3; j++) {
  38.             if (i - dx[j] >= 0 && d[i - dx[j]].first != INF){
  39.                 if (d[i].first > d[i - dx[j]].first + 1) {
  40.                     d[i] = d[i - dx[j]];
  41.                     d[i].first++;
  42.                     p[i] = i - dx[j];
  43.                 }
  44.                 else {
  45.                     if (d[i].first == d[i - dx[j]].first + 1 && d[i].second > d[i - dx[j]].second) {
  46.                         d[i] = d[i - dx[j]];
  47.                         d[i].first++;
  48.                         p[i] = i - dx[j];
  49.                     }
  50.                 }
  51.             }
  52.         }
  53.         if (s[i] == '"') {
  54.             d[i].second++;
  55.         }
  56.     }
  57.     if (d[n - 1].first == INF) {
  58.         cout << -1;
  59.         return 0;
  60.     }
  61.     cout << d[n - 1].first << ' ' << d[n - 1].second << endl;
  62.     vector<int> r;
  63.     int c = n - 1;
  64.     while (c != 0) {
  65.         r.push_back(c);
  66.         c = p[c];
  67.     }
  68.     r.push_back(0);
  69.     for (int i = r.size() - 1; i >= 0; i--) {
  70.         cout << r[i] + 1 << ' ';
  71.     }
  72.  
  73.     return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement