fork download
copy 
  1. // Brute-force correct solution (C++)
  2. // Works for moderate n (n up to a few thousands comfortably).
  3. // For n up to 2e5 this will be too slow; nếu cần bản tối ưu mình sẽ viết tiếp.
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. using int64 = long long;
  7.  
  8. int main(){
  9.     ios::sync_with_stdio(false);
  10.     cin.tie(nullptr);
  11.     int n;
  12.     if(!(cin >> n)) return 0;
  13.     vector<char> c(n);
  14.     vector<int64> d(n);
  15.     for(int i=0;i<n;i++){
  16.         cin >> c[i] >> d[i];
  17.     }
  18.  
  19.     // position: 0..n-1
  20.     vector<int64> T(n);
  21.     for(int i=0;i<n;i++) T[i] = 2LL * d[i]; // scale times by 2 as in analysis
  22.  
  23.     vector<int64> ans(n, 0);
  24.  
  25.     for(int i=0;i<n;i++){
  26.         for(int j=i+1;j<n;j++){
  27.             if(c[i] == c[j]) continue; // only opposite directions meet
  28.             int64 xi = i;
  29.             int64 xj = j;
  30.             int64 D = (xj - xi + n) % n; // clockwise distance i->j in [0..n-1]
  31.             if(D == 0) D = n; // defensive, though initial positions are distinct
  32.             int64 minT = min(T[i], T[j]);
  33.             if(minT < D) continue;
  34.             int64 meets = (minT - D) / n + 1;
  35.             ans[i] += meets;
  36.             ans[j] += meets;
  37.         }
  38.     }
  39.  
  40.     for(int i=0;i<n;i++){
  41.         cout << ans[i] << '\n';
  42.     }
  43.     return 0;
  44. }
  45.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
6
+4
-5
-5
+5
+5
-3
stdout
copy 
5
6
6
5
5
3
https://ideone.com/xdLaIh
language:
C++14 (gcc 8.3)
created:
1 day 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!