SHARE
TWEET

Untitled

a guest Feb 18th, 2020 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. vector<vector<int> > a, gr;
  8. vector<int> ans;
  9. vector<bool> used;
  10. int n;
  11.  
  12. void dfs(int v){
  13.     used[v] = true;
  14.     for (int i : gr[v]){
  15.         if (!used[i]){
  16.             dfs(i);
  17.         }
  18.     }
  19.     ans.push_back(v);
  20. }
  21.  
  22. int main(){
  23.     ios_base::sync_with_stdio(false);
  24.     cin.tie(0);
  25.     cout.tie(0);
  26.     cin >> n;
  27.     a.resize(n);
  28.     gr.resize(n);
  29.     used.resize(n);
  30.     a.assign(n, vector<int>(4));
  31.     for (int i = 0; i < n; ++i){
  32.         cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
  33.     }
  34.     for (int i = 0; i < n; ++i){
  35.         for (int j = 0; j < n; ++j){
  36.             if (i == j){
  37.                 continue;
  38.             }
  39.             if (a[i][0] > a[j][1] || a[i][1] < a[j][0]){
  40.                 continue;
  41.             }
  42.             if (a[i][0] < a[j][0] && a[i][1] > a[j][1]){
  43.                 if (a[j][2] == a[i][2] + (a[j][0] - a[i][0]) * a[i][3]){
  44.                     if (a[j][2]+a[j][3] >= a[j][3] + a[i][2] + (a[j][0] - a[i][0]) * a[i][3]){
  45.                         gr[i].push_back(j);
  46.                     }
  47.                 }else if (a[j][2] > a[i][2] + (a[j][0] - a[i][0]) * a[i][3]){
  48.                     gr[i].push_back(j);
  49.                 }
  50.                 continue;
  51.             }
  52.             if (a[i][0] >= a[j][0]){
  53.                 if (a[i][2] == a[j][2]+(a[i][0] - a[j][0]) * a[j][3]){
  54.                     if (a[i][2]+a[i][3] < a[j][3]+a[j][2]+(a[i][0] - a[j][0]) * a[j][3]){
  55.                         gr[i].push_back(j);
  56.                     }
  57.                 }
  58.                 else if (a[i][2] < a[j][2]+(a[i][0] - a[j][0]) * a[j][3]){
  59.                     gr[i].push_back(j);
  60.                 }
  61.             }else{
  62.                 if (a[i][2]+((a[i][1]-a[i][0])*a[i][3]) < a[j][2]+(a[i][1] - a[j][0]) * a[j][3]){
  63.                     gr[i].push_back(j);
  64.                 }
  65.             }
  66.         }
  67.     }
  68.     for (int i = 0; i < n; ++i){
  69.         if (!used[i]){
  70.             dfs(i);
  71.         }
  72.     }
  73.     reverse(ans.begin(), ans.end());
  74.     for (int i:ans){
  75.         cout << i+1 << ' ';
  76.     }
  77.     return 0;
  78. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top