Gecko [ tsuru-no-tsurugi.tokyo ]

Name	Size	Permission	Date
A-cpp	174 B	-rwxr-xr--	2024-08-28 22:43
A-python-2.py	45 B	-rw-r--r--	2024-08-28 22:43
A-python.py	129 B	-rwxr-xr--	2024-08-28 22:43
B-cpp	210 B	-rw-r--r--	2024-08-28 22:43
B-python.py	118 B	-rw-r--r--	2024-08-28 22:43
C-cpp	242 B	-rw-r--r--	2024-08-28 22:43
D-cpp	242 B	-rw-r--r--	2024-08-28 22:43
D-python.py	160 B	-rw-r--r--	2024-08-28 22:43
E-cpp1	595 B	-rw-r--r--	2024-08-28 22:43
E-cpp2	164 B	-rw-r--r--	2024-08-28 22:43
E-python.py	337 B	-rw-r--r--	2024-08-28 22:43
F-cpp	563 B	-rwxr-xr--	2024-08-28 22:43
G-cpp	480 B	-rwxr-xr--	2024-08-28 22:43
H-cpp	1018 B	-rw-r--r--	2024-08-28 22:43
I-cpp	1.59 KB	-rw-r--r--	2024-08-28 22:43
J-cpp	1.16 KB	-rw-r--r--	2024-08-28 22:43
K-cpp	2.04 KB	-rwxr-xr--	2024-08-28 22:43

Rename

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> a(8,0);

vector<pair<int,int>> p(8,{-1,0});
vector<pair<int,int>> temp;
vector<int> win_tour(16,-1);
vector<pair<int,double>> tour(16,{0,1});

void win_update(int lpos,int bit){
  if(bit){
    win_tour[lpos/2] = win_tour[lpos];
  }
  else{
    win_tour[lpos/2] = win_tour[lpos+1];
  }
}

void tour_update(int lpos,int bit){
  if(tour[lpos].first==0 && tour[lpos+1].first==0){
    tour[lpos/2].first = 0;
    tour[lpos/2].second = 1;
    return;
  }
  if(tour[lpos].first==0){
    tour[lpos/2].first = tour[lpos+1].first;
    tour[lpos/2].second = tour[lpos+1].second;
    return;
  }
  if(tour[lpos+1].first==0){
    tour[lpos/2].first = tour[lpos].first;
    tour[lpos/2].second = tour[lpos].second;
    return;
  }
  if(bit){
    tour[lpos/2].first = tour[lpos].first;
    tour[lpos/2].second = tour[lpos].second*tour[lpos+1].second*(double)tour[lpos].first/(double)(tour[lpos].first+tour[lpos+1].first);
  } 
  else{
    tour[lpos/2].first = tour[lpos+1].first;
    tour[lpos/2].second = tour[lpos].second*tour[lpos+1].second*(double)tour[lpos+1].first/(double)(tour[lpos].first+tour[lpos+1].first);
  }
}

bool judge(int x){
  p[0].second = x;
  double sum = 0;
  double cnt = 0;
  do{
    for(int i=8;i<=15;i++) win_tour[i] = p[i-8].first;
    for(int i=8;i<=15;i++) tour[i] = make_pair(p[i-8].second,(double)1);
    for(int bit=0;bit<(1<<7);bit++){
      for(int i=14;i>0;i-=2) win_update(i,(bit>>(i/2)) & 1);
      for(int i=14;i>0;i-=2) tour_update(i,(bit>>(i/2)) & 1);
      if(win_tour[1]==0) sum += tour[1].second;
      if(win_tour[1]!=-1)cnt += tour[1].second;
    }
  }while (next_permutation(p.begin(), p.end()));
  if(sum/cnt >= (double)0.5) return true;
  else return false;
}

int main() {
  cin >> n;
  for(int i=0;i<=n;i++) p[i].first=i;
  for(int i=1;i<=n;i++) cin >> a[i];
  for(int i=1;i<=n;i++) p[i].second = a[i];
  temp = p;
  int l=0,r=9000;
  while(l<r){
    int m = (l+r)/2;
    if(judge(m)) r=m;
    else l=m+1;
    p = temp;
  }
  if(l>8640) cout << -1 << endl;
  else cout << l << endl;
}