From 4570bdbae3c2d59031eed95b7e89c00ac176be52 Mon Sep 17 00:00:00 2001
From: Aditya Naik
Date: Fri, 11 May 2018 17:02:52 -0400
Subject: tried buddies

---
 12356/buddies.c  | 53 ++++++++++++++++++++++++++++++++++++++---------------
 12356/buddies.in | 33 +++++++++++++++++++++++++++++++++
 2 files changed, 71 insertions(+), 15 deletions(-)
 create mode 100644 12356/buddies.in

diff --git a/12356/buddies.c b/12356/buddies.c
index 43cabf1..e93fc98 100644
--- a/12356/buddies.c
+++ b/12356/buddies.c
@@ -4,36 +4,59 @@ int main(){
     int s, r;
     scanf("%d %d", &s, &r);
     while(s>0){
-	int line[100000]={0}, i;
-	for(i=0; i<s; i++)
-	    line[i]=1;
-
-	int left, right;
 
+	int left, right, i;
+	int gapsl[100000], gapsr[100000], gap_index=0;	
+	
 	while(r--){
-	    int left_seek, right_seek;
+	    int left_seek, right_seek, curr_gapindex;
 	    
 	    scanf("%d %d", &left, &right);
+
+	    left--; right--; /* adjust for 0 index */
 	    
-	    for(i=left-1; i<right; i++)
-		line[i]=0;
-	    
-	    for(left_seek=left-1; line[left_seek]==0
-		    && left_seek>0; left_seek--);
-	    for(right_seek=right-1; line[right_seek]==0
-		    && right_seek<s; right_seek++);
+	    curr_gapindex = gap_index++;	    
+	    gapsl[curr_gapindex]=left;
+	    gapsr[curr_gapindex]=right;
+
+	    left_seek=left-1;
+	    right_seek=right+1;
 	    
-	    if(left_seek<=0 && line[left_seek]==0)
+	    int gap_collision=0;
+	    for(i=0; i<=curr_gapindex; i++){
+		while(gapsl[i]<=left_seek && gapsr[i]>=left_seek){
+		    left_seek--;
+		    gap_collision=1;
+		}
+		if(gap_collision){  
+		    i=-1;
+		    gap_collision=0;
+		}
+	    }
+	    if(left_seek<0)
 		printf("* ");
 	    else
 		printf("%d ", left_seek+1);
 
-	    if(right_seek==s && line[right_seek]==0)
+	    gap_collision=0;
+	    for(i=0; i<=curr_gapindex; i++){
+		while(gapsr[i]>=right_seek && gapsl[i]<=right_seek){
+		    right_seek++;
+		    gap_collision=1;
+		}
+		if(gap_collision){
+		    i=-1;
+		    gap_collision=0;
+		}
+	    }
+	    if(right_seek>=s)
 		printf("*\n");
 	    else
 		printf("%d\n", right_seek+1);
 	}
+	
 	printf("-\n");
 	scanf("%d %d", &s, &r);
     }
+    return 0;
 }
diff --git a/12356/buddies.in b/12356/buddies.in
new file mode 100644
index 0000000..3d4e4e6
--- /dev/null
+++ b/12356/buddies.in
@@ -0,0 +1,33 @@
+1 1
+1 1
+10 4
+2 5
+6 9
+1 1
+10 10
+5 1
+1 1
+10 4
+1 7
+8 8
+9 9
+10 10
+10 5
+5 10
+4 4
+2 2
+3 3
+1 1
+10 5
+2 2
+3 5
+8 8
+9 10
+1 1
+2 1
+1 2
+100000 3
+2 999
+5600 8472
+99001 99999
+0 0
-- 
cgit v1.2.3