fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using FileName = string;
  5. using ChangeID = string;
  6. using RepoID = int;
  7.  
  8. struct Commit {
  9.     int commitID;
  10.     int timestamp;
  11.     vector<pair<FileName, ChangeID>> changes;
  12.  
  13.     bool operator<(const Commit& other) const {
  14.         if (timestamp == other.timestamp) {
  15.             return commitID < other.commitID;
  16.         }
  17.         return timestamp < other.timestamp;
  18.     }
  19. };
  20.  
  21. ostream& operator<<(ostream& os, const Commit& c) {
  22.     return os << c.commitID;
  23. }
  24.  
  25. // Global structures
  26. unordered_map<ChangeID, RepoID> change_to_repo;
  27. unordered_map<RepoID, unordered_map<FileName, ChangeID>> repo_to_changes;
  28. map<RepoID, set<Commit>> repo_to_commits;
  29. set<RepoID> ambiguous_repos;
  30.  
  31. vector<Commit> commits;
  32.  
  33. // -------------------- PARSE --------------------
  34. vector<Commit> retrieveCommits() {
  35.     int N;
  36.     cin >> N;
  37.     cin.ignore();
  38.  
  39.     vector<Commit> result;
  40.  
  41.     for (int i = 0; i < N; i++) {
  42.         string line;
  43.         getline(cin, line);
  44.         if (line.empty()) continue;
  45.  
  46.         stringstream ss(line);
  47.  
  48.         string tmp;
  49.         int id, timestamp;
  50.  
  51.         // id X timestamp Y
  52.         if (!(ss >> tmp >> id >> tmp >> timestamp)) continue;
  53.  
  54.         vector<pair<FileName, ChangeID>> changes;
  55.         string file, change;
  56.  
  57.         while (ss >> file >> change) {
  58.             changes.emplace_back(file, change);
  59.         }
  60.  
  61.         result.push_back({id, timestamp, changes});
  62.     }
  63.  
  64.     return result;
  65. }
  66.  
  67. // -------------------- ADD COMMIT --------------------
  68. void add_commit(const Commit& commit, RepoID repo) {
  69.     auto& repoChanges = repo_to_changes[repo];
  70.  
  71.     for (const auto& p : commit.changes) {
  72.         const FileName& fileName = p.first;
  73.         const ChangeID& changeId = p.second;
  74.  
  75.         // map change -> repo
  76.         change_to_repo[changeId] = repo;
  77.  
  78.         auto it = repoChanges.find(fileName);
  79.         if (it != repoChanges.end()) {
  80.             // conflict => ambiguous
  81.             if (it->second != changeId) {
  82.                 ambiguous_repos.insert(repo);
  83.             }
  84.         } else {
  85.             repoChanges[fileName] = changeId;
  86.         }
  87.     }
  88.  
  89.     repo_to_commits[repo].insert(commit);
  90. }
  91.  
  92. // -------------------- QUERIES --------------------
  93. void answerQueries() {
  94.     int Q;
  95.     cin >> Q;
  96.  
  97.     while (Q--) {
  98.         int start, end;
  99.         FileName fileName;
  100.         ChangeID changeID;
  101.  
  102.         cin >> start >> end >> fileName >> changeID;
  103.  
  104.         auto itRepo = change_to_repo.find(changeID);
  105.  
  106.         // not found
  107.         if (itRepo == change_to_repo.end()) {
  108.             cout << "\n";
  109.             continue;
  110.         }
  111.  
  112.         RepoID repo = itRepo->second;
  113.  
  114.         // ambiguous repo
  115.         if (ambiguous_repos.count(repo)) {
  116.             cout << "AMBIGUOUS\n";
  117.             continue;
  118.         }
  119.  
  120.         auto& s = repo_to_commits[repo];
  121.  
  122.         Commit lower{INT_MIN, start, {}};
  123.         Commit upper{INT_MAX, end, {}};
  124.  
  125.         auto it1 = s.lower_bound(lower);
  126.         auto it2 = s.upper_bound(upper);
  127.  
  128.         bool first = true;
  129.         for (auto it = it1; it != it2; ++it) {
  130.             if (!first) cout << " ";
  131.             cout << it->commitID;
  132.             first = false;
  133.         }
  134.  
  135.         cout << "\n";
  136.     }
  137. }
  138.  
  139. // -------------------- MAIN --------------------
  140. int main() {
  141.     commits = retrieveCommits();
  142.  
  143.     RepoID next_repo_id = 0;
  144.  
  145.     for (const auto& commit : commits) {
  146.         RepoID matched_repo = next_repo_id;
  147.  
  148.         // find existing repo via ANY changeID
  149.         for (const auto& change : commit.changes) {
  150.             auto it = change_to_repo.find(change.second);
  151.             if (it != change_to_repo.end()) {
  152.                 matched_repo = it->second;
  153.                 break;
  154.             }
  155.         }
  156.  
  157.         if (matched_repo == next_repo_id) {
  158.             next_repo_id++;
  159.         }
  160.  
  161.         add_commit(commit, matched_repo);
  162.     }
  163.  
  164.     answerQueries();
  165. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Sample Input

6
id 8 timestamp 200 quicksort.cpp 839ad0 mergesort.cpp 0cdde1 bubblesort.cpp 248dd1
id 0 timestamp 500 array.h 163111 sequence.h 294d3f
id 6 timestamp 200 mergesort.cpp 0cdde1 bogosort.cpp 4213ff
id 4 timestamp 100 array.h 163111 vector.h fcc2af
id 2 timestamp 300 bubblesort.cpp 248dd1 bogosort.cpp 4213ff
id 3 timestamp 300 bubblesort.cpp eaf88a bogosort.cpp 4f11aa

4
0 10000 quicksort.cpp 839ad0
0 500 vector.h fcc2af
0 100000 no_found.h empty_response
100 200 bogosort.cpp 4213ff
stdout
copy 
Standard output is empty
https://ideone.com/E1OtdY
language:
C++14 (clang 8.0)
created:
3 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!