Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <string>
- #include <stack>
- #include <set>
- #include <map>
- #define pii pair <int,int>
- #define vec vector
- using namespace std;
- using ll = long long;
- using ld = long double;
- using db = double;
- void cv(vector <int> &v){
- for (auto x: v) cout<<x<<' ';
- cout<<"\n";
- }
- void cvl(vector <ll> &v){
- for (auto x: v) cout<<x<<' ';
- cout<<"\n";
- }
- void cvv(vector <vector <int> > &v){
- for (auto x: v) cv(x);
- cout<<"\n";
- }
- int n;
- struct el{
- int a,b, c,d;
- };
- void mk(el &x){
- cin>>x.a>>x.b>>x.c>>x.d;
- }
- int tm(el x, int p){
- return x.c + x.d * (p - x.a);
- }
- int inter(el x, el y){
- if (y.b >= x.a && y.a < x.a){
- //p = min(x.b, y.b);
- return 1;
- }
- if (y.a <= x.b && y.b > x.b){
- //p = max(x.a, y.a);
- return 2;
- }
- return 0;
- }
- vector <el> v;
- vector <vector <int> > G;
- void mkG(){
- el x,y;
- int p;
- G.resize(n);
- for (int i = 0; i < n;++i){
- x = v[i];
- for (int j = 0; j < n && j != i ; ++ j){
- p = -1;
- y = v[j];
- if (inter(x,y) == 1){
- p = min(x.b, y.b);
- if (tm(x,p) == tm(y,p)){
- p--;
- }
- if (p < x.a || p < y.a){
- p = -1;
- }
- }
- else if (inter(x,y) == 2){
- p = max(x.a, y.a);
- if (tm(x,p) == tm(y,p)){
- p++;
- }
- if (p > x.b || p > y.b) {
- p=-1;
- }
- }
- if (p != -1){
- if (tm(x,p) < tm(y,p)){
- G[i].push_back(j);
- }
- else if (tm(x,p) > tm(y,p)){
- G[j].push_back(i);
- }
- }
- }
- }
- }
- const int wh=0, gr=1, bl=2;
- vector <int> clr;
- vector <int> ans;
- void dfs(int v) {
- clr[v] = gr;
- for (int u: G[v]){
- if (clr[u] == wh){
- dfs(u);
- }
- }
- clr[v] = bl;
- ans.push_back(v+1);
- }
- int main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin>>n;
- v.resize(n);
- for (int i=0;i<n;++i) mk(v[i]);
- mkG();
- clr.assign(n, wh);
- for (int i = 0; i < n;++i){
- if (clr[i] == wh) dfs(i);
- }
- reverse(ans.begin(), ans.end());
- cv(ans);
- }
- /*
- 3
- 1 10 3 4
- 3 5 3 4
- 10 11 10 1
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement