---
# System prepended metadata

title: '題解 zerojudge h082: 2. 贏家預測 APCS'
tags: [APCS, vector, c++]

---

###### tags: `APCS` `c++` `vector`
# 題解 zerojudge h082: 2. 贏家預測 APCS
## vector
```cpp=
#include<bits/stdc++.h>
using namespace std;
int S[1005],T[1005],l[1005]={0};
vector<int>r,win,lose;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m,k;
    cin>>n>>m;
    for(int i=1;i<=n;i++)   cin>>S[i];
    for(int i=1;i<=n;i++)   cin>>T[i];
    for(int i=0;i<n;i++){cin>>k;r.push_back(k);}

    long long a,b,c,d;
    while(r.size()>1){
        win.clear();lose.clear();
        for(int i=0;i<r.size()-1;i+=2){
            a=S[r[i]];b=T[r[i]];
            c=S[r[i+1]];d=T[r[i+1]];
            if(a*b>=c*d){
                S[r[i]]=a+(c*d)/(2*b);T[r[i]]=b+(c*d)/(2*a);
                S[r[i+1]]=c+c/2;T[r[i+1]]=d+d/2;
                win.push_back(r[i]);
                l[r[i+1]]++;
                if(l[r[i+1]]<m) lose.push_back(r[i+1]);
            }
            else{
                S[r[i]]=a+a/2;T[r[i]]=b+b/2;
                S[r[i+1]]=c+(a*b)/(2*d);T[r[i+1]]=d+(a*b)/(2*c);
                win.push_back(r[i+1]);
                l[r[i]]++;
                if(l[r[i]]<m) lose.push_back(r[i]);
            }
        }
        if(r.size()&1)//有奇數個，有人烙單
            win.push_back(r[r.size()-1]);
        r.clear();
        r.insert(r.end(),win.begin(),win.end());
        r.insert(r.end(),lose.begin(),lose.end());
    }
    cout<<*r.begin();
}

```