fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. // Function to count substrings containing at least one '*'
  9. long long countMaliciousSubstrings(const string& password) {
  10.     long long total = 0;
  11.     int n = password.size();
  12.     int lastClean = -1;
  13.  
  14.     for (int i = 0; i < n; ++i) {
  15.         if (password[i] == '*') {
  16.             int len = i - lastClean - 1;
  17.             total += (1LL * len * (len + 1)) / 2;
  18.             lastClean = i;
  19.         }
  20.     }
  21.  
  22.     int len = n - lastClean - 1;
  23.     total += (1LL * len * (len + 1)) / 2;
  24.  
  25.     long long totalSubstrings = (1LL * n * (n + 1)) / 2;
  26.     return totalSubstrings - total;
  27. }
  28.  
  29. // Main function to find minimum time after which password becomes irrecoverable
  30. int minTimeToIrrecoverable(string password, vector<int>& attackOrder, long long m) {
  31.     int n = password.size();
  32.     int left = 1, right = n, ans = n + 1;
  33.  
  34.     while (left <= right) {
  35.         int mid = (left + right) / 2;
  36.         string temp = password;
  37.  
  38.         // Simulate attack for 'mid' seconds
  39.         for (int i = 0; i < mid; ++i) {
  40.             temp[attackOrder[i]] = '*';
  41.         }
  42.  
  43.         long long malicious = countMaliciousSubstrings(temp);
  44.  
  45.         if (malicious >= m) {
  46.             ans = mid;
  47.             right = mid - 1;
  48.         } else {
  49.             left = mid + 1;
  50.         }
  51.     }
  52.  
  53.     return (ans == n + 1) ? -1 : ans;
  54. }
  55.  
  56. // Example usage
  57. int main() {
  58.     string password;
  59.     int n;
  60.     long long m;
  61.  
  62.     cout << "Enter password: ";
  63.     cin >> password;
  64.  
  65.     cout << "Enter number of attack indices: ";
  66.     cin >> n;
  67.  
  68.     vector<int> attackOrder(n);
  69.     cout << "Enter attack order (0-indexed): ";
  70.     for (int i = 0; i < n; ++i) {
  71.         cin >> attackOrder[i];
  72.     }
  73.  
  74.     cout << "Enter m (number of substrings with '*'): ";
  75.     cin >> m;
  76.  
  77.     int result = minTimeToIrrecoverable(password, attackOrder, m);
  78.     cout << "Minimum time to become irrecoverable: " << result << endl;
  79.  
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
bcdb
4
2
4
1
3
10
stdout
copy 
Enter password: Enter number of attack indices: Enter attack order (0-indexed): Enter m (number of substrings with '*'): Minimum time to become irrecoverable: -1
https://ideone.com/fN0wDj
language:
C++ (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!