[HOJ] 363 拉麵比較

單淘汰賽

#include<cstdio>
#include<algorithm>
#include<vector>
#include"interactive/363.h"
using namespace std;
struct node{
    int val,nxt;
};
vector<node> mn,mx;
int n,k,now,siz,a[]={1,2,3,4,5};
/*int Compare(int x,int y){
    if(a[x]>a[y])return 1;
    else return -1;
}
void Answer(int X,int Y){
    printf("%d %d\n",X,Y);
}
int Ramen(){
    return 5;
}*/
int main (){
    n=Ramen();
    siz=(n+1>>1)-1;
    for(int i=0;i<n-1;i+=2){
        k=Compare(i,i+1);
        if(k==1){
            mx.push_back(node{i,i/2+1});
            mn.push_back(node{i+1,i/2+1});
        }
        else {
            mn.push_back(node{i,i/2+1});
            mx.push_back(node{i+1,i/2+1});
        }
    }
    if(n%2){
        mx.push_back(node{n-1,0});
        mn.push_back(node{n-1,0});
    }
    mn[siz].nxt=mx[siz].nxt=0;
    while(siz--){
        k=Compare(mn[now].val,mn[mn[now].nxt].val);
        if(k==1)swap(mn[now].val,mn[mn[now].nxt].val);
        mn[now].nxt=mn[mn[now].nxt].nxt;
 
        k=Compare(mx[now].val,mx[mx[now].nxt].val);
        if(k==-1)swap(mx[now].val,mx[mx[now].nxt].val);
        now=mx[now].nxt=mx[mx[now].nxt].nxt;
    }
    Answer(mn[now].val,mx[now].val);
}