为啥o(n^2)能A

#include<cstdio>
#include<map> 
#include<algorithm>
#include<string.h>
#define N 100005

using namespace std;

int num[N], snum[N], n, loc[N], tag[N]; // loc存储，num对应位置的元素在排序后的新下标值！tag标记对应的排序后的下标值是否被使用过 

int check(int f){
    // 寻找左侧第一个f值对应的没有使用过的下标值
    int l = 1, r = n, mid, ans;
    while(l<=r){
        mid = (l+r)>>1;
        if( snum[mid] == f && tag[mid] == 0){
            ans = mid; // 记录答案 
            r = mid-1; // 去左区间寻找 
        }
        else if(snum[mid] == f && tag[mid] == 1){
            l = mid+1; // 去右区间寻找 
        }else if( snum[mid] > f)    
            r = mid-1; // 去左区间寻找 
        else
            l = mid+1;
    } 

    tag[ans]=1; // 标记

    return  ans;
} 

int main(void)
{
    int i, j;
    scanf("%d", &n);
    for(i=1;i<=n;i++){
        scanf("%d", num+i);
        snum[i] = num[i];
    }    

    sort(snum+1, snum+n+1); // 升序排序

    for(i=1;i<=n;i++)   loc[i] = check( num[i] ); // 得到从原下标到新有序下标的映射 

    // 求中位数
    memset(tag, 0, sizeof(tag)); // 清空
    tag[ loc[1] ] = 1; // 第一个元素
    printf("%d\n", num[1]);

    int now = loc[1]; // 当前中位数( 映射后的下标值 ) 
    int a, b, tmp;

    for(i=1;i<(n+1)/2;i++, puts("")){  // 剩余一共 n/2 次，这里不对，n不一定是奇数！ 
        a = loc[i*2];
        b = loc[i*2+1]; // a和b是新加入的两个数的映射下标值

        if(a > b)   swap(a,b); // a为小的数，b为大的数 

        if( a < now && b > now  ){ // 1. 
            printf("%d", snum[now]); // 中位数不变 
        }else if ( b < now ){
            // 2. 两个数都比now小，寻找now左侧第一个数(二分)，这里不能二分好像！不对！！！！没有办法二分啊！ 

            tmp = now;
            for(j=now-1;j>0;j--){
                if( tag[j] ){
                    tmp = j;
                    break; 
                }
            }

            if( b < tmp && tmp != now){  // 都比j小，则中位数就是j 
                printf("%d", snum[tmp]);
                now = tmp; // 中位数 
            }else{
                // 其它情况，则中位数是较大的那个数b
                printf("%d", snum[b]);
                now = b;
            }
        } else {
            // 2. 两个数都比now大，寻找now右侧第一个数(二分)，这里不能二分好像！不对！！！！没有办法二分啊！ 
            tmp = now;
            for(j=now+1;j<=n;j++){
                if( tag[j] ){
                    tmp = j;
                    break;
                }
            }

            if( a > tmp && tmp != now){  // 都比r大，则中位数就是r 
                printf("%d", snum[tmp]);
                now = tmp; // 中位数 
            }else{
                // 其它情况，则中位数是较小的那个数a 
                printf("%d", snum[a]);
                now = a;
            }
        } 

        tag[a]=1;
        tag[b]=1; // 标记新加入的两个数 
    } 
    return 0;
}