fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define x first
  4. #define y second
  5. #define dbg(x) cout << #x << '=' << x << '\n';
  6. #define ll long long
  7. #define pi pair<int,int>
  8. #define pl pair<long long,long long>
  9. #define rd(x) cin >> x;
  10. #define rda(a,n) for(int i=1;i<=n;i++) cin >> a[i];
  11. #define wr(x) cout << x << ' ';
  12. #define wrl(x) cout << x << '\n';
  13. #define wra(a,n) for(int i=1;i<=n;i++) cout << a[i] << ' '; cout << '\n';
  14. #define lg length()
  15. ifstream in("file.in");
  16. ofstream out("file.out");
  17. #define MAXN 100005
  18. #define INF 1000000005
  19. #define LINF 1000000000000000005
  20. struct comp{
  21.     bool operator()(int a, int b){
  22.         return a>b;
  23.     }
  24. };
  25.  
  26. ///________CODE_STARTS_HERE________\\\
  27.  
  28. struct rekt{
  29.     int x1,y1,x2,y2,pos;
  30. } a[500005],b[500005];
  31.  
  32. vector <int> g[500005];
  33.  
  34. bool cx1(rekt a, rekt b){
  35.     if(a.x1<b.x1) return true;
  36.     else if(a.x1>b.x1) return false;
  37.     else if(a.y2<=b.y2) return true;
  38.     else return false;
  39. }
  40.  
  41. bool cx2(rekt a, rekt b){
  42.     if(a.x2<b.x2) return true;
  43.     else if(a.x2>b.x2) return false;
  44.     else if(a.y1<=b.y1) return true;
  45.     else return false;
  46. }
  47.  
  48. bool cy1(rekt a, rekt b){
  49.     if(a.y1<b.y1) return true;
  50.     else if(a.y1>b.y1) return false;
  51.     else if(a.x2<=b.x1) return true;
  52.     else return false;
  53. }
  54.  
  55. bool cy2(rekt a, rekt b){
  56.     if(a.y2<b.y2) return true;
  57.     else if(a.y2>b.y2) return false;
  58.     else if(a.x1<=b.x1) return true;
  59.     else return false;
  60. }
  61.  
  62. int n,col[500005],can[5],v[500005];
  63.  
  64. void DFS(int nod){
  65.     if(v[nod]) return;
  66.     v[nod]=1;
  67.     bool can[5];
  68.     for(int i : g[nod]){
  69.         DFS(i);
  70.         can[col[i]]=1;
  71.     }
  72.     for(int i=1;i<=4;i++){
  73.         if(!can[i]) {
  74.             col[nod]=i;
  75.             break;
  76.         }
  77.     }
  78. }
  79.  
  80. int main(){
  81.     ios_base :: sync_with_stdio(0); cin.tie(NULL);
  82.     cin >> n;
  83.     for(int i=1;i<=n;i++){
  84.         cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
  85.         a[i].pos=i;
  86.     }
  87.     for(int i=1;i<=n;i++){
  88.         if(a[i].x1>a[i].x2){
  89.             swap(a[i].x1,a[i].x2);
  90.         }
  91.         if(a[i].y1>a[i].y2){
  92.             swap(a[i].y1,a[i].y2);
  93.         }
  94.         b[i]=a[i];
  95.     }
  96.     sort(a+1,a+n+1,cx1);
  97.     sort(b+1,b+n+1,cx2);
  98.     int p=1;
  99.     for(int i=1;i<=n;i++){
  100.         while(a[p].x1<b[i].x2 && p<=n) p++;
  101.         if(p>n || a[p].x1>b[i].x2) continue;
  102.         while(a[p].y2<=b[i].y1 && p<=n && a[p+1].x1==b[i].x2) p++;
  103.         if(p>n) continue;
  104.         while(a[p].y2>b[i].y1 && a[p].y1<b[i].y2 && p<=n && a[p].x1==b[i].x2){
  105.             g[b[i].pos].push_back(a[p].pos);
  106.             g[a[p].pos].push_back(b[i].pos);
  107.             p++;
  108.         }
  109.         p--;
  110.     }
  111.     sort(a+1,a+n+1,cy1);
  112.     sort(b+1,b+n+1,cy2);
  113.     p=1;
  114.     for(int i=1;i<=n;i++){
  115.         while(a[p].y1<b[i].y2 && p<=n) p++;
  116.         if(p>n || a[p].y1>b[i].y2) continue;
  117.         while(a[p].x2<=b[i].x1 && p<=n && a[p+1].y1==b[i].y2) p++;
  118.         if(p>n) continue;
  119.         while(a[p].x2>b[i].x1 && a[p].x1<b[i].x2 && p<=n && a[p].y1==b[i].y2){
  120.             g[b[i].pos].push_back(a[p].pos);
  121.             g[a[p].pos].push_back(b[i].pos);
  122.             p++;
  123.         }
  124.         p--;
  125.     }
  126.     /*for(int i=1;i<=n;i++){
  127.         cout << i << ": ";
  128.         for(int j : g[i]){
  129.             cout << j << ' ';
  130.         }
  131.     cout << '\n';
  132.     }*/
  133.     for(int i=1;i<=n;i++){
  134.         DFS(i);
  135.         if(!col[i]){
  136.             cout << "NO";
  137.             return 0;
  138.         }
  139.     }
  140.     cout << "YES\n";
  141.     for(int i=1;i<=n;i++){
  142.         cout << col[i] << '\n';
  143.     }
  144. }
  145.  
Success #stdin #stdout 0s 32768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
https://ideone.com/qCzgE4
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!