fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. pair<int,int>a[1000001];
  5. int id1[1000001],id2[1000001];
  6. vector<int>id[1000001];
  7. bool cmp(int x,int y){
  8.     return a[x].second<a[y].second;
  9. }
  10. int l[1000001],r[1000001];
  11. bool ans[1000001];
  12. void process(){
  13.     for(int i=1;i<1000001;i++){
  14.         if(id[i].empty())continue;
  15.         sort(id[i].begin(),id[i].end(),cmp);
  16.         l[i]=0;
  17.         ans[id[i][0]]=1;
  18.         if(!id1[a[id[i][0]].second]){
  19.             id1[a[id[i][0]].second]=i;
  20.         }
  21.         else if(!id2[a[id[i][0]].second]){
  22.             id2[a[id[i][0]].second]=i;
  23.         }
  24.         else{
  25.             int u=id2[a[id[i][0]].second];
  26.             id2[a[id[i][0]].second]=i;
  27.             while(1){
  28.                 if(l[u]==r[u]){
  29.                     ans[id[u][l[u]]]=0;
  30.                     break;
  31.                 }
  32.                 bool ok=1;
  33.                 if(id1[a[id[u][l[u]]].second]!=u&&id2[a[id[u][l[u]]].second]!=u){
  34.                     ans[id[u][l[u]]]=0;
  35.                     l[u]++;
  36.                     if(id1[a[id[u][l[u]]].second]==u||id2[a[id[u][l[u]]].second]==u)ok=1;
  37.                     else if(!id1[a[id[u][l[u]]].second]){
  38.                         id1[a[id[u][l[u]]].second]=u;
  39.                         ans[id[u][l[u]]]=1;
  40.                     }
  41.                     else if(!id2[a[id[u][l[u]]].second]){
  42.                         id2[a[id[u][l[u]]].second]=u;
  43.                         if(id1[a[id[u][l[u]]].second]>id2[a[id[u][l[u]]].second]){
  44.                             swap(id1[a[id[u][l[u]]].second],id2[a[id[u][l[u]]].second]);
  45.                         }
  46.                         ans[id[u][l[u]]]=1;
  47.                     }
  48.                     else{
  49.                         ok=0;
  50.                         if(u<id1[a[id[u][l[u]]].second]){
  51.                             ans[id[u][l[u]]]=1;
  52.                             swap(u,id1[a[id[u][l[u]]].second]);
  53.                         }
  54.                         else if(u>id2[a[id[u][l[u]]].second]){
  55.                             ans[id[u][l[u]]]=1;
  56.                             swap(u,id2[a[id[u][l[u]]].second]);
  57.                         }
  58.                     }
  59.                 }
  60.                 else{
  61.                     ans[id[u][r[u]]]=0;
  62.                     r[u]--;
  63.                     if(id1[a[id[u][r[u]]].second]==u||id2[a[id[u][r[u]]].second]==u)ok=1;
  64.                     else if(!id1[a[id[u][r[u]]].second]){
  65.                         id1[a[id[u][r[u]]].second]=u;
  66.                         ans[id[u][r[u]]]=1;
  67.                     }
  68.                     else if(!id2[a[id[u][r[u]]].second]){
  69.                         id2[a[id[u][r[u]]].second]=u;
  70.                         if(id1[a[id[u][r[u]]].second]>id2[a[id[u][r[u]]].second]){
  71.                             swap(id1[a[id[u][r[u]]].second],id2[a[id[u][r[u]]].second]);
  72.                         }
  73.                         ans[id[u][r[u]]]=1;
  74.                     }
  75.                     else{
  76.                         ok=0;
  77.                         if(u<id1[a[id[u][r[u]]].second]){
  78.                             ans[id[u][r[u]]]=1;
  79.                             swap(u,id1[a[id[u][r[u]]].second]);
  80.                         }
  81.                         else if(u>id2[a[id[u][r[u]]].second]){
  82.                             ans[id[u][r[u]]]=1;
  83.                             swap(u,id2[a[id[u][r[u]]].second]);
  84.                         }
  85.                     }
  86.                 }
  87.                 if(ok)break;
  88.             }
  89.         }
  90.         r[i]=id[i].size()-1;
  91.         if(id[i].size()==1)continue;
  92.         ans[id[i][r[i]]]=1;
  93.         if(!id1[a[id[i][r[i]]].second]){
  94.             id1[a[id[i][r[i]]].second]=i;
  95.         }
  96.         else if(!id2[a[id[i][r[i]]].second]){
  97.             id2[a[id[i][r[i]]].second]=i;
  98.         }
  99.         else{
  100.             int u=id2[a[id[i][r[i]]].second];
  101.             id2[a[id[i][r[i]]].second]=i;
  102.             while(1){
  103.                 if(l[u]==r[u]){
  104.                     ans[id[u][l[u]]]=0;
  105.                     break;
  106.                 }
  107.                 bool ok=1;
  108.                 if(id1[a[id[u][l[u]]].second]!=u&&id2[a[id[u][l[u]]].second]!=u){
  109.                     ans[id[u][l[u]]]=0;
  110.                     l[u]++;
  111.                     if(id1[a[id[u][l[u]]].second]==u||id2[a[id[u][l[u]]].second]==u)ok=1;
  112.                     else if(!id1[a[id[u][l[u]]].second]){
  113.                         id1[a[id[u][l[u]]].second]=u;
  114.                         ans[id[u][l[u]]]=1;
  115.                     }
  116.                     else if(!id2[a[id[u][l[u]]].second]){
  117.                         id2[a[id[u][l[u]]].second]=u;
  118.                         if(id1[a[id[u][l[u]]].second]>id2[a[id[u][l[u]]].second]){
  119.                             swap(id1[a[id[u][l[u]]].second],id2[a[id[u][l[u]]].second]);
  120.                         }
  121.                         ans[id[u][l[u]]]=1;
  122.                     }
  123.                     else{
  124.                         ok=0;
  125.                         if(u<id1[a[id[u][l[u]]].second]){
  126.                             ans[id[u][l[u]]]=1;
  127.                             swap(u,id1[a[id[u][l[u]]].second]);
  128.                         }
  129.                         else if(u>id2[a[id[u][l[u]]].second]){
  130.                             ans[id[u][l[u]]]=1;
  131.                             swap(u,id2[a[id[u][l[u]]].second]);
  132.                         }
  133.                     }
  134.                 }
  135.                 else{
  136.                     ans[id[u][r[u]]]=0;
  137.                     r[u]--;
  138.                     if(id1[a[id[u][r[u]]].second]==u||id2[a[id[u][r[u]]].second]==u)ok=1;
  139.                     else if(!id1[a[id[u][r[u]]].second]){
  140.                         id1[a[id[u][r[u]]].second]=u;
  141.                         ans[id[u][r[u]]]=1;
  142.                     }
  143.                     else if(!id2[a[id[u][r[u]]].second]){
  144.                         id2[a[id[u][r[u]]].second]=u;
  145.                         if(id1[a[id[u][r[u]]].second]>id2[a[id[u][r[u]]].second]){
  146.                             swap(id1[a[id[u][r[u]]].second],id2[a[id[u][r[u]]].second]);
  147.                         }
  148.                         ans[id[u][r[u]]]=1;
  149.                     }
  150.                     else{
  151.                         ok=0;
  152.                         if(u<id1[a[id[u][r[u]]].second]){
  153.                             ans[id[u][r[u]]]=1;
  154.                             swap(u,id1[a[id[u][r[u]]].second]);
  155.                         }
  156.                         else if(u>id2[a[id[u][r[u]]].second]){
  157.                             ans[id[u][r[u]]]=1;
  158.                             swap(u,id2[a[id[u][r[u]]].second]);
  159.                         }
  160.                     }
  161.                 }
  162.                 if(ok)break;
  163.             }
  164.         }
  165.     }
  166.     for(int i=1;i<=n;i++)cout<<ans[i];
  167. }      
  168. void init(){
  169.     cin>>n;
  170.     for(int i=1;i<=n;i++){
  171.         cin>>a[i].first>>a[i].second;
  172.         id[a[i].first].push_back(i);
  173.     }
  174. }   
  175. int main(){
  176.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  177.     #define NAME "nazunasdish"
  178.     if(fopen(NAME".inp","r")){
  179.         freopen(NAME".inp","r",stdin);
  180.         freopen(NAME".out","w",stdout);
  181.     }
  182.     // clock_t beg=clock();
  183.     init();
  184.     process();
  185.     // cerr<<double(clock()-beg)/CLOCKS_PER_SEC;
  186. }
Success #stdin #stdout 0.02s 28256KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/85BcJU
slamp
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

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!