diff options
| -rw-r--r-- | 12356/buddies.c | 53 | ||||
| -rw-r--r-- | 12356/buddies.in | 33 |
2 files changed, 71 insertions, 15 deletions
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 |