fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ---------- Core solution ----------
  5. struct FastHashLL {
  6.     size_t operator()(long long x) const noexcept {
  7.         x += 0x9e3779b97f4a7c15LL;
  8.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9LL;
  9.         x = (x ^ (x >> 27)) * 0x94d049bb133111ebLL;
  10.         x = x ^ (x >> 31);
  11.         return (size_t)x;
  12.     }
  13. };
  14.  
  15. struct DSU {
  16.     vector<int> parent, sz;
  17.     vector<long long> mn, mx;
  18.     vector<char> printed;
  19.  
  20.     int make_node(long long idx) {
  21.         int id = (int)parent.size();
  22.         parent.push_back(id);
  23.         sz.push_back(1);
  24.         mn.push_back(idx);
  25.         mx.push_back(idx);
  26.         printed.push_back(0);
  27.         return id;
  28.     }
  29.     int find(int x) {
  30.         while (parent[x] != x) {
  31.             parent[x] = parent[parent[x]];
  32.             x = parent[x];
  33.         }
  34.         return x;
  35.     }
  36.     int unite(int a, int b) {
  37.         a = find(a); b = find(b);
  38.         if (a == b) return a;
  39.         if (sz[a] < sz[b]) swap(a, b);
  40.         parent[b] = a;
  41.         sz[a] += sz[b];
  42.         mn[a] = min(mn[a], mn[b]);
  43.         mx[a] = max(mx[a], mx[b]);
  44.         printed[a] = printed[a] || printed[b];
  45.         return a;
  46.     }
  47. };
  48.  
  49. vector<string> solve(int N, vector<vector<string>> Messages) {
  50.     vector<string> out;
  51.     out.reserve(N);
  52.  
  53.     DSU dsu;
  54.     unordered_map<long long, int, FastHashLL> letterId; letterId.reserve(N*2);
  55.     unordered_map<long long, char, FastHashLL> letterAt; letterAt.reserve(N*2);
  56.     unordered_set<long long, FastHashLL> starAt; starAt.reserve(N*2);
  57.  
  58.     auto emit_if_ready = [&](int root) {
  59.         root = dsu.find(root);
  60.         if (dsu.printed[root]) return;
  61.         long long L = dsu.mn[root], R = dsu.mx[root];
  62.         if (dsu.sz[root] != (int)(R - L + 1)) return;            // not contiguous
  63.         if (!starAt.count(L - 1) || !starAt.count(R + 1)) return; // not enclosed
  64.         string s; s.reserve(dsu.sz[root]);
  65.         for (long long i = L; i <= R; ++i) s.push_back(letterAt[i]);
  66.         dsu.printed[root] = 1;
  67.         out.push_back(move(s));
  68.     };
  69.  
  70.     for (int i = 0; i < N; ++i) {
  71.         long long idx = stoll(Messages[i][0]);
  72.         char ch = Messages[i][1][0];
  73.  
  74.         if (ch == '*') {
  75.             starAt.insert(idx);
  76.             vector<pair<long long,string>> newly;
  77.  
  78.             auto try_side = [&](long long neighbor, bool starIsLeftBoundary) {
  79.                 auto it = letterId.find(neighbor);
  80.                 if (it == letterId.end()) return;
  81.                 int root = dsu.find(it->second);
  82.                 long long L = dsu.mn[root], R = dsu.mx[root];
  83.  
  84.                 // star must touch the boundary of the block
  85.                 if (starIsLeftBoundary && L != neighbor) return;
  86.                 if (!starIsLeftBoundary && R != neighbor) return;
  87.  
  88.                 if (dsu.printed[root]) return;
  89.                 if (dsu.sz[root] != (int)(R - L + 1)) return; // gaps exist
  90.                 bool enclosed = starIsLeftBoundary ? starAt.count(R + 1)
  91.                                                    : starAt.count(L - 1);
  92.                 if (!enclosed) return;
  93.  
  94.                 string s; s.reserve(dsu.sz[root]);
  95.                 for (long long x = L; x <= R; ++x) s.push_back(letterAt[x]);
  96.                 dsu.printed[root] = 1;
  97.                 newly.push_back({L, move(s)});
  98.             };
  99.  
  100.             // a new star can close up to two messages (one on each side)
  101.             try_side(idx + 1, true);
  102.             try_side(idx - 1, false);
  103.  
  104.             if (!newly.empty()) {
  105.                 sort(newly.begin(), newly.end(),
  106.                      [](const auto& a, const auto& b){ return a.first < b.first; });
  107.                 for (auto& p : newly) out.push_back(move(p.second));
  108.             }
  109.         } else {
  110.             if (letterAt.find(idx) != letterAt.end()) continue; // safety
  111.             letterAt[idx] = ch;
  112.             int id = dsu.make_node(idx);
  113.             letterId[idx] = id;
  114.             auto itL = letterId.find(idx - 1);
  115.             if (itL != letterId.end()) id = dsu.unite(id, itL->second);
  116.             auto itR = letterId.find(idx + 1);
  117.             if (itR != letterId.end()) id = dsu.unite(id, itR->second);
  118.             emit_if_ready(id); // may complete an enclosed block
  119.         }
  120.     }
  121.     return out;
  122. }
  123.  
  124. // ---------- Driver ----------
  125. int main() {
  126.     ios::sync_with_stdio(false);
  127.     cin.tie(nullptr);
  128.  
  129.     int N;
  130.     if (!(cin >> N)) return 0;
  131.  
  132.     vector<vector<string>> Messages;
  133.     Messages.reserve(N);
  134.     for (int i = 0; i < N; ++i) {
  135.         string idx, ch;
  136.         cin >> idx >> ch;                 // index_number and character as strings
  137.         Messages.push_back({idx, ch});
  138.     }
  139.  
  140.     vector<string> ans = solve(N, Messages);
  141.     for (const string& s : ans) cout << s << '\n';
  142.     return 0;
  143. }
  144.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/K9s888
language:
C++ (gcc 8.3)
created:
24 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!