Advertisement
Sreekar_0125

Untitled

Feb 22nd, 2024
653
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.87 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>    
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. template <class T>
  7. using pbds =
  8.     tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  9. // #define cerr if(false)cerr
  10. #define int long long
  11. #define pb push_back
  12. #define F first
  13. #define S second
  14. #define yes cout << "Yes\n"
  15. #define no cout << "No\n"
  16. #define yn(x) x ? yes : no
  17. #define f(i, s, e) for (int i = s; i < e; i++)
  18. #define vi vector<int>
  19. #define vb vector<bool>
  20. #define pii pair<int, int>
  21. #define vpi vector<pii>
  22. #define umi unordered_map<int, int>
  23. #define mi map<int, int>
  24. #define si set<int>
  25. #define sc set<char>
  26. #define maxheap priority_queue<int>
  27. #define minheap priority_queue<int, vector<int>, greater<int>>
  28. #define all(x) x.begin(), x.end()
  29. #define minele(x) *min_element(all(x))
  30. #define maxele(x) *max_element(all(x))
  31. #define endl '\n'
  32.  
  33. const int N = 2e5;
  34. const int MOD = 1e9 + 7;
  35.  
  36.  
  37. #ifndef ONLINE_JUDGE
  38. #define debug(x)            \
  39.     cerr << (#x) << " is "; \
  40.     _print(x)
  41. #define dbg(x)              \
  42.     cerr << (#x) << " is " << x << endl;
  43. #else
  44. #define debug(x)
  45. #define dbg(x)
  46. #endif
  47.  
  48.  
  49. template <typename T>
  50. void _print(T a)
  51. {
  52.     cerr << a;
  53. }
  54. template <typename T>
  55. void print(T a)
  56. {
  57.     cout << a << ' ';
  58. }
  59. template <typename T>
  60. void println(T a)
  61. {
  62.     cout << a << endl;
  63. }
  64. template <class T>
  65. istream &operator>>(istream &is, vector<T> &a)
  66. {
  67.     for (auto &x : a)
  68.         is >> x;
  69.     return is;
  70. }
  71. template <class T>
  72. ostream &operator<<(ostream &os, const vector<T> &a)
  73. {
  74.     for (const auto &x : a)
  75.         os << x << ' ';
  76.     return os;
  77. }
  78.  
  79. template <class T, class V>
  80. void _print(pair<T, V> p);
  81. template <class T>
  82. void _print(vector<T> v);
  83. template <class T>
  84. void _print(set<T> v);
  85. template <class T, class V>
  86. void _print(map<T, V> v);
  87. template <class T>
  88. void _print(multiset<T> v);
  89. template <class T, class V>
  90. void _print(pair<T, V> p)
  91. {
  92.     cerr << "{";
  93.     _print(p.F);
  94.     cerr << ",";
  95.     _print(p.S);
  96.     cerr << "} ";
  97. }
  98. template <class T>
  99. void _print(vector<T> v)
  100. {
  101.     cerr << "[ ";
  102.     for (T i : v)
  103.     {
  104.         _print(i);
  105.         cerr << " ";
  106.     }
  107.     cerr << "]";
  108.     cerr << endl;
  109. }
  110. template <class T>
  111. void _print(set<T> v)
  112. {
  113.     cerr << "[ ";
  114.     for (T i : v)
  115.     {
  116.         _print(i);
  117.         cerr << " ";
  118.     }
  119.     cerr << "]";
  120.     cerr << endl;
  121. }
  122. template <class T>
  123. void _print(multiset<T> v)
  124. {
  125.     cerr << "[ ";
  126.     for (T i : v)
  127.     {
  128.         _print(i);
  129.         cerr << " ";
  130.     }
  131.     cerr << "]";
  132.     cerr << endl;
  133. }
  134. template <class T, class V>
  135. void _print(map<T, V> v)
  136. {
  137.     cerr << "[ ";
  138.     for (auto i : v)
  139.     {
  140.         _print(i);
  141.         cerr << " ";
  142.     }
  143.     cerr << "]";
  144.     cerr << endl;
  145. }
  146. template <class T, class V>
  147. void _print(unordered_map<T, V> v)
  148. {
  149.     cerr << "[ ";
  150.     for (auto i : v)
  151.     {
  152.         _print(i);
  153.         cerr << " ";
  154.     }
  155.     cerr << "]";
  156.     cerr << endl;
  157. }
  158.  
  159. /////////////Sieve///////////////
  160. // vb sieve(N + 5, true);
  161. // vi primes;
  162. // void gensieve()
  163. // {
  164. //     sieve[0] = sieve[1] = false;
  165. //     for (int i = 2; i <= sqrt(N); i++)
  166. //     {
  167. //         if (sieve[i])
  168. //         {
  169. //             for (int j = i * i; j <= N; j += i)
  170. //                 sieve[j] = false;
  171. //         }
  172. //     }
  173. //     for (int i = 2; i <= N; i++)
  174. //     {
  175. //         if (sieve[i])
  176. //             primes.pb(i);
  177. //     }
  178. // }
  179. ////////////////////////////////
  180.  
  181. int binpow(int a, int b)
  182. {
  183.     int ans = 1;
  184.     a %= MOD;
  185.     while(b)
  186.     {
  187.         if(b & 1)
  188.             ans = ((ans % MOD) * (a % MOD)) % MOD;
  189.        
  190.         a = ((a % MOD) * (a % MOD)) % MOD;
  191.         b >>= 1;
  192.     }
  193.     return ans;
  194. }
  195.  
  196. void fast()
  197. {
  198.     ios_base::sync_with_stdio(false);
  199.     cin.tie(NULL);
  200.     cout.tie(NULL);
  201. }
  202.  
  203. void init_code()
  204. {
  205. #ifndef ONLINE_JUDGE
  206.     freopen("input.txt", "r", stdin);
  207.     freopen("output.txt", "w", stdout);
  208.     freopen("error.txt", "w", stderr);
  209. #endif // ONLINE_JUDGE
  210. }
  211.  
  212. void solve()
  213. {
  214.     int no_of_jobs;
  215.     cin >> no_of_jobs;
  216.  
  217.     int no_of_workers = 2;
  218.  
  219.    
  220.     vector<pair<pii, int>> times(no_of_jobs);
  221.     // vi duration(no_of_jobs);
  222.     // cin >> duration;
  223.     // cin >> tin >> tout;
  224.     map<int, vi> mp;
  225.     for(int i = 0; i < no_of_jobs; i++)
  226.     {
  227.         int st, et, dur;
  228.         cin >> st >> et >> dur;
  229.    
  230.         times[i].F = {st, et};
  231.         times[i].S = i + 1;
  232.         mp[i + 1].pb(st);
  233.         mp[i + 1].pb(et);
  234.         mp[i + 1].pb(dur);
  235.     }
  236.  
  237.     sort(all(times));
  238.     debug(times);
  239.  
  240.     int worker_1 = -2, worker_2 = -1;
  241.     vi skipped;
  242.  
  243.     map<int, vector<vi>> scheduled_jobs;
  244.  
  245.     for(int i = 0; i < no_of_jobs; i++)
  246.     {
  247.         int st = times[i].F.F;
  248.         int et = times[i].F.S;
  249.         int job_id = times[i].S;
  250.         int dur = mp[job_id][2];
  251.  
  252.         // if(worker_1 < worker)
  253.  
  254.         if((worker_1 < worker_2) && worker_1 < et - dur)
  255.         {
  256.             int est_st = max(st, worker_1 + 1);
  257.             int est_et = est_st + dur;
  258.             vi schedule;
  259.             schedule.pb(job_id);
  260.             schedule.pb(est_st);
  261.             schedule.pb(est_et);
  262.             scheduled_jobs[1].pb(schedule);
  263.  
  264.             worker_1 = est_et;
  265.         }
  266.         else if (worker_2 < et - dur)
  267.         {
  268.             int est_st = max(st, worker_2 + 1);
  269.             int est_et = est_st + dur;
  270.             vi schedule;
  271.             schedule.pb(job_id);
  272.             schedule.pb(est_st);
  273.             schedule.pb(est_et);
  274.             scheduled_jobs[2].pb(schedule);
  275.  
  276.             worker_2 = est_et;
  277.         }
  278.         else
  279.         {
  280.             skipped.pb(job_id);
  281.         }
  282.     }  
  283.     debug(scheduled_jobs);
  284. }
  285.  
  286. signed main()
  287. {
  288.     init_code();
  289.     fast();
  290.     int t = 1;
  291.     // cin >> t;
  292.     while (t--)
  293.     {
  294.         solve();
  295.     }
  296.     return 0;
  297. }
  298.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement