fork(3) download
copy 
  1. #include <cstdio>
  2. using namespace std;
  3.  
  4.  
  5. int main(void){
  6.  
  7.     int n,i,t,test,pos,s,v,temp,size,offset,off2;
  8.     long long int ll;
  9.  
  10.     scanf("%d",&n);
  11.     int *p=new int[2*n];// megoldast tarolom itt
  12.     int *coords=new int[4*n];// input koordinatakhoz
  13.     int *cnt=new int[n+1];
  14.     int *id=new int[n];
  15.     long long int *A=new long long int[n+1];// kupac (legfeljebb) n elemu, de szamozas 1-tol kezdodik!
  16.  
  17.     for(i=0;i<4*n;i++)scanf("%d",&coords[i]);
  18.  
  19.     for(test=1,t=0;test&&t<2;t++){
  20.       // elemek rendezese bal vegpont szerint novekvo sorrendben O(n) idoben
  21.       for(i=0;i<=n;i++)cnt[i]=0;
  22.       for(i=0;i<n;i++)cnt[coords[4*i+t]]++;
  23.       for(s=0,i=1;i<=n;i++){temp=cnt[i];cnt[i]=s;s+=temp;}
  24.       for(i=0;i<n;i++){v=coords[4*i+t];id[cnt[v]]=i;cnt[v]++;}
  25.  
  26.       for(pos=i=size=0;i<n;i++){
  27.          while(pos<n&&coords[4*id[pos]+t]==i+1){
  28. 	       ll=coords[4*id[pos]+t+2];
  29. 	       ll=(ll<<20)+id[pos];// felso 20 biten a jobb vegpont koordinataja, also 20 biten az (eredeti) pozicio tarolasa
  30. 	       pos++;
  31. 	       for(size++,offset=size;offset>1&&A[offset>>1]>ll;A[offset]=A[offset>>1],offset>>=1);// uj elem hozzaadasa a kupachoz, kupacot a jobb vegpont szerint rendezem
  32. 	       A[offset]=ll;
  33. 	 }
  34. 	 // itt a kupac mindegyik elemenek bal vegpontja kisebb, mint (i+1), igy, ha megoldhato a feladat, akkor
  35. 	 // olyan megoldas is van, amiben a kupac legkisebb elemenel (i+1)-et valasztottunk a bastya (megfelelo) koordinatajanak
  36. 	 // azaz a moho algoritmus itt mukodik
  37.  
  38. 	 if(size==0){test=0;break;}// kupacom ures, nem megoldhato a feladat
  39. 	 ll=A[1];// ez a legkisebb elem a kupacban
  40. 	 if((ll>>20)<i+1){test=0;break;}// kupac legkisebb elemenek jobb vegpontja kisebb, mint (i+1), feladat nem megoldhato
  41. 	 p[2*(ll&1048575)+t]=i+1;// megoldas koordinatajanak tarolasa
  42.  
  43. 	 ll=A[size];
  44. 	 size--;
  45. 	 offset=1;
  46. 	 while(1){// elem sullyesztese a kupacban
  47. 	       off2=2*offset;
  48. 	       if(off2>size)break;
  49. 	       if(off2<size&&A[off2]>A[off2+1])off2++;
  50. 	       if(A[off2]>ll)break;
  51. 	       A[offset]=A[off2];
  52. 	       offset=off2;
  53. 	 }
  54. 	 A[offset]=ll;
  55.     }}    
  56.  
  57.     if(test){for(i=0;i<n;i++)printf("%d %d\n",p[2*i],p[2*i+1]);}
  58.     else printf("NEM\n");
  59.  
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
4
1 1 1 1
1 3 2 4
3 1 4 2
2 2 4 4
stdout
copy 
1 1
2 3
3 2
4 4
https://ideone.com/cfZHQ9
S82 feladat
language:
C++ (gcc 8.3)
created:
10 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!