fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. using namespace std;
  5.  
  6. int countIntersections(const string &s) {
  7.     map<char, vector<int>> positions;
  8.     int n = s.size();
  9.  
  10.     // Lưu vị trí xuất hiện của từng ký tự
  11.     for (int i = 0; i < n; i++) {
  12.         positions[s[i]].push_back(i);
  13.     }
  14.  
  15.     int intersections = 0;
  16.     vector<pair<int, int>> segments;
  17.  
  18.     // Tạo danh sách các đoạn nối
  19.     for (const auto &entry : positions) {
  20.         segments.push_back({entry.second[0], entry.second[1]});
  21.     }
  22.  
  23.     // Đếm số giao điểm
  24.     int m = segments.size();
  25.     for (int i = 0; i < m; i++) {
  26.         for (int j = i + 1; j < m; j++) {
  27.             int a1 = segments[i].first, a2 = segments[i].second;
  28.             int b1 = segments[j].first, b2 = segments[j].second;
  29.             if ((a1 < b1 && b1 < a2 && a2 < b2) || (b1 < a1 && a1 < b2 && b2 < a2)) {
  30.                 intersections++;
  31.             }
  32.         }
  33.     }
  34.  
  35.     return intersections;
  36. }
  37.  
  38. int main() {
  39.     string s;
  40.     cin >> s;
  41.     cout << countIntersections(s) << endl;
  42.     return 0;
  43. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/KslQhf
language:
C++ (gcc 8.3)
created:
4 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!