Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- template <class T>
- using pbds =
- tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- // #define cerr if(false)cerr
- #define int long long
- #define pb push_back
- #define F first
- #define S second
- #define yes cout << "Yes\n"
- #define no cout << "No\n"
- #define yn(x) x ? yes : no
- #define f(i, s, e) for (int i = s; i < e; i++)
- #define vi vector<int>
- #define vb vector<bool>
- #define pii pair<int, int>
- #define vpi vector<pii>
- #define umi unordered_map<int, int>
- #define mi map<int, int>
- #define si set<int>
- #define sc set<char>
- #define maxheap priority_queue<int>
- #define minheap priority_queue<int, vector<int>, greater<int>>
- #define all(x) x.begin(), x.end()
- #define minele(x) *min_element(all(x))
- #define maxele(x) *max_element(all(x))
- #define endl '\n'
- const int N = 2e5;
- const int MOD = 1e9 + 7;
- #ifndef ONLINE_JUDGE
- #define debug(x) \
- cerr << (#x) << " is "; \
- _print(x)
- #define dbg(x) \
- cerr << (#x) << " is " << x << endl;
- #else
- #define debug(x)
- #define dbg(x)
- #endif
- template <typename T>
- void _print(T a)
- {
- cerr << a;
- }
- template <typename T>
- void print(T a)
- {
- cout << a << ' ';
- }
- template <typename T>
- void println(T a)
- {
- cout << a << endl;
- }
- template <class T>
- istream &operator>>(istream &is, vector<T> &a)
- {
- for (auto &x : a)
- is >> x;
- return is;
- }
- template <class T>
- ostream &operator<<(ostream &os, const vector<T> &a)
- {
- for (const auto &x : a)
- os << x << ' ';
- return os;
- }
- template <class T, class V>
- void _print(pair<T, V> p);
- template <class T>
- void _print(vector<T> v);
- template <class T>
- void _print(set<T> v);
- template <class T, class V>
- void _print(map<T, V> v);
- template <class T>
- void _print(multiset<T> v);
- template <class T, class V>
- void _print(pair<T, V> p)
- {
- cerr << "{";
- _print(p.F);
- cerr << ",";
- _print(p.S);
- cerr << "} ";
- }
- template <class T>
- void _print(vector<T> v)
- {
- cerr << "[ ";
- for (T i : v)
- {
- _print(i);
- cerr << " ";
- }
- cerr << "]";
- cerr << endl;
- }
- template <class T>
- void _print(set<T> v)
- {
- cerr << "[ ";
- for (T i : v)
- {
- _print(i);
- cerr << " ";
- }
- cerr << "]";
- cerr << endl;
- }
- template <class T>
- void _print(multiset<T> v)
- {
- cerr << "[ ";
- for (T i : v)
- {
- _print(i);
- cerr << " ";
- }
- cerr << "]";
- cerr << endl;
- }
- template <class T, class V>
- void _print(map<T, V> v)
- {
- cerr << "[ ";
- for (auto i : v)
- {
- _print(i);
- cerr << " ";
- }
- cerr << "]";
- cerr << endl;
- }
- template <class T, class V>
- void _print(unordered_map<T, V> v)
- {
- cerr << "[ ";
- for (auto i : v)
- {
- _print(i);
- cerr << " ";
- }
- cerr << "]";
- cerr << endl;
- }
- /////////////Sieve///////////////
- // vb sieve(N + 5, true);
- // vi primes;
- // void gensieve()
- // {
- // sieve[0] = sieve[1] = false;
- // for (int i = 2; i <= sqrt(N); i++)
- // {
- // if (sieve[i])
- // {
- // for (int j = i * i; j <= N; j += i)
- // sieve[j] = false;
- // }
- // }
- // for (int i = 2; i <= N; i++)
- // {
- // if (sieve[i])
- // primes.pb(i);
- // }
- // }
- ////////////////////////////////
- int binpow(int a, int b)
- {
- int ans = 1;
- a %= MOD;
- while(b)
- {
- if(b & 1)
- ans = ((ans % MOD) * (a % MOD)) % MOD;
- a = ((a % MOD) * (a % MOD)) % MOD;
- b >>= 1;
- }
- return ans;
- }
- void fast()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- }
- void init_code()
- {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- freopen("error.txt", "w", stderr);
- #endif // ONLINE_JUDGE
- }
- void solve()
- {
- int no_of_jobs;
- cin >> no_of_jobs;
- int no_of_workers = 2;
- vector<pair<pii, int>> times(no_of_jobs);
- // vi duration(no_of_jobs);
- // cin >> duration;
- // cin >> tin >> tout;
- map<int, vi> mp;
- for(int i = 0; i < no_of_jobs; i++)
- {
- int st, et, dur;
- cin >> st >> et >> dur;
- times[i].F = {st, et};
- times[i].S = i + 1;
- mp[i + 1].pb(st);
- mp[i + 1].pb(et);
- mp[i + 1].pb(dur);
- }
- sort(all(times));
- debug(times);
- int worker_1 = -2, worker_2 = -1;
- vi skipped;
- map<int, vector<vi>> scheduled_jobs;
- for(int i = 0; i < no_of_jobs; i++)
- {
- int st = times[i].F.F;
- int et = times[i].F.S;
- int job_id = times[i].S;
- int dur = mp[job_id][2];
- // if(worker_1 < worker)
- if((worker_1 < worker_2) && worker_1 < et - dur)
- {
- int est_st = max(st, worker_1 + 1);
- int est_et = est_st + dur;
- vi schedule;
- schedule.pb(job_id);
- schedule.pb(est_st);
- schedule.pb(est_et);
- scheduled_jobs[1].pb(schedule);
- worker_1 = est_et;
- }
- else if (worker_2 < et - dur)
- {
- int est_st = max(st, worker_2 + 1);
- int est_et = est_st + dur;
- vi schedule;
- schedule.pb(job_id);
- schedule.pb(est_st);
- schedule.pb(est_et);
- scheduled_jobs[2].pb(schedule);
- worker_2 = est_et;
- }
- else
- {
- skipped.pb(job_id);
- }
- }
- debug(scheduled_jobs);
- }
- signed main()
- {
- init_code();
- fast();
- int t = 1;
- // cin >> t;
- while (t--)
- {
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement