fork download
copy 
  1. /*
  2.     Problem: Final Black Positions After Executing Prefix Commands
  3.     Company Tag: GrowthJockey
  4.  
  5.     Problem Statement:
  6.         We have task positions from 1 to 10^9.
  7.  
  8.         Some positions are initially black.
  9.         All other positions are white.
  10.  
  11.         We are given a command string s.
  12.  
  13.         For every prefix of s, a new worker starts at position 1.
  14.  
  15.         Commands:
  16.             A -> move from x to x + 1
  17.             B -> move from x to the nearest white position strictly greater than x
  18.  
  19.         After each worker finishes, the final position becomes black.
  20.  
  21.         We need to print all black positions at the end.
  22.  
  23.     Constraints:
  24.         1 <= n, m <= 2 * 10^5
  25.         1 <= initialBlack[i] <= 10^9
  26.         s contains only characters 'A' and 'B'
  27.         The task range is too large to use a direct array.
  28.  
  29.     Simple Brute Force:
  30.         For each prefix, simulate the whole prefix from position 1.
  31.  
  32.     Why Brute Force Fails:
  33.         There are O(n) prefixes.
  34.         Simulating every prefix from scratch can take O(n^2).
  35.  
  36.     Better Idea:
  37.         Use a DSU-like next pointer to quickly find the next white position.
  38.  
  39.         findWhite(x) gives the smallest white position >= x.
  40.  
  41.         When a position becomes black:
  42.             we link it to the next white position.
  43.  
  44.         This lets us skip already black positions efficiently.
  45.  
  46.     Dry Run:
  47.         s = "ABAA"
  48.         initially black = {2}
  49.  
  50.         Worker 1:
  51.             A -> 2
  52.             black = {2}
  53.  
  54.         Worker 2:
  55.             A -> 2
  56.             B -> 3
  57.             black = {2, 3}
  58.  
  59.         Worker 3:
  60.             A -> 2
  61.             B -> 4
  62.             A -> 5
  63.             black = {2, 3, 5}
  64.  
  65.         Worker 4:
  66.             Final position becomes 6
  67.  
  68.         Final black positions:
  69.             2 3 5 6
  70.  
  71.     Time Complexity:
  72.         O((n + m) log(n + m))
  73.  
  74.     Space Complexity:
  75.         O(n + m)
  76. */
  77.  
  78. #include <bits/stdc++.h>
  79. using namespace std;
  80.  
  81. class NextWhiteFinder {
  82. public:
  83.     unordered_map<long long, long long> parent;
  84.  
  85.     long long findWhite(long long x) {
  86.         vector<long long> path;
  87.  
  88.         // Keep jumping while x is already black.
  89.         while (parent.find(x) != parent.end()) {
  90.             path.push_back(x);
  91.             x = parent[x];
  92.         }
  93.  
  94.         // Compress the path so future searches become faster.
  95.         for (long long node : path) {
  96.             parent[node] = x;
  97.         }
  98.  
  99.         return x;
  100.     }
  101.  
  102.     void markBlack(long long x) {
  103.         // Once x becomes black, the next possible white position starts from x + 1.
  104.         parent[x] = findWhite(x + 1);
  105.     }
  106. };
  107.  
  108. int main() {
  109.     int n, m;
  110.     cin >> n >> m;
  111.  
  112.     string s;
  113.     cin >> s;
  114.  
  115.     NextWhiteFinder dsu;
  116.     set<long long> black;
  117.  
  118.     for (int i = 0; i < m; i++) {
  119.         long long x;
  120.         cin >> x;
  121.  
  122.         black.insert(x);
  123.         dsu.markBlack(x);
  124.     }
  125.  
  126.     long long previousFinal = 1;
  127.  
  128.     for (int i = 0; i < n; i++) {
  129.         long long currentPosition;
  130.  
  131.         if (i == 0) {
  132.             currentPosition = 1;
  133.         } else {
  134.             currentPosition = previousFinal;
  135.  
  136.             /*
  137.                 If the previous command was B, then the previous final position
  138.                 was found as a white position and then marked black.
  139.                 So now we need to move to the next white position.
  140.             */
  141.             if (s[i - 1] == 'B') {
  142.                 currentPosition = dsu.findWhite(currentPosition + 1);
  143.             }
  144.         }
  145.  
  146.         if (s[i] == 'A') {
  147.             currentPosition++;
  148.         } else {
  149.             currentPosition = dsu.findWhite(currentPosition + 1);
  150.         }
  151.  
  152.         // Add the final position of this worker to the black set.
  153.         if (black.insert(currentPosition).second) {
  154.             dsu.markBlack(currentPosition);
  155.         }
  156.  
  157.         previousFinal = currentPosition;
  158.     }
  159.  
  160.     cout << black.size() << endl;
  161.  
  162.     for (long long x : black) {
  163.         cout << x << " ";
  164.     }
  165.  
  166.     cout << endl;
  167.  
  168.     return 0;
  169. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/FPRbQx
language:
C++14 (gcc 8.3)
created:
5 hours 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!