Submission #1323882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1323882		SmuggingSpun	Koala Game (APIO17_koala)	C++20	100 / 100	35 ms	456 KiB

koala

#include "koala.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>bool maximize(T& a, T b){
  if(a < b){
    a = b;
    return true;
  }
  return false;
}
const int lim = 105;
int n, w, tmp1[lim], tmp2[lim];
vector<int>play_round(vector<int>b){
  for(int i = 0; i < n; i++){
    tmp1[i] = b[i];
  }
  playRound(tmp1, tmp2);
  for(int i = 0; i < n; i++){
    b[i] = tmp2[i];
  }
  return b;
}
namespace sub1{
  int solve(){
    vector<int>b(n, 0);
    b[0] = 1;
    if((b = play_round(b))[0] < 2){
      return 0;
    }
    return find(b.begin(), b.end(), 0) - b.begin();
  }
}
int minValue(int _n, int _w){
  n = _n;
  w = _w;
  return sub1::solve();
}
namespace sub2{
  int solve(){
    vector<int>p(n);
    iota(p.begin(), p.end(), 0);
    while(p.size() > 1){
      int d = n / p.size();
      vector<int>b(n, 0);
      for(int& i : p){
        b[i] = d;
      }
      b = play_round(b);
      vector<int>np;
      for(int& i : p){
        if(b[i] > d){
          np.push_back(i);
        }
      }
      swap(p, np);
    }
    return p[0];
  }
}
int maxValue(int _n, int _w){
  n = _n;
  w = _w;
  return sub2::solve();
}
namespace sub3{
  int solve(){
    vector<int>ICR = {5, 2, 1};
    if(n == 6){
      ICR = {2, 1, 1};
    }
    for(int bit = 0, z = 0; bit < 3; bit++){
      int nz = z + ICR[bit];
      vector<int>b(n, 0);
      b[0] = b[1] = nz;
      b = play_round(b);
      if(b[0] <= nz && b[1] > nz){
        return 1;
      }
      if(b[0] > nz && b[1] <= nz){
        return 0;
      }
      if(b[0] > nz && b[1] > nz){
        z = nz;
      }
      else if(bit == 2 && n > 6){
        ICR[bit - 1]++;
      }
    }
  }
}
int greaterValue(int _n, int _w){
  n = _n;
  w = _w;
  return sub3::solve();
}
namespace sub4{
  vector<int>solve(){
    vector<int>p(n), ans(n);
    iota(p.begin(), p.end(), 0);
    stable_sort(p.begin(), p.end(), [&] (int i, int j){
      vector<int>b(n, 0);
      b[i] = b[j] = w >> 1;
      b = play_round(b);
      return b[j] > (w >> 1);
    });
    for(int i = 0; i < n; i++){
      ans[p[i]] = i + 1;
    }
    return ans;
  }
}
namespace sub5{
  const int lim = 105;
  bitset<lim>trace[lim];
  bool check(int l, int r, int d){
    vector<pair<int, int>>dp(n + 1, make_pair(0, 0));
    for(int i = 1; i <= n; i++){
      int cost = i < l || i > r ? 1 : d + 1;
      trace[i].reset();
      for(int j = n; j >= cost; j--){
        if(maximize(dp[j], make_pair(dp[j - cost].first + i, dp[j - cost].second + 1))){
          trace[i][j] = true; 
        }
      }
    }
    int cnt = 0;
    for(int i = n, j = n; i > 0; i--){
      if(trace[i][j]){
        if(l <= i && r >= i){
          cnt++;
          j -= d + 1;
        }
        else{
          j--;
        }
      }
    }
    return cnt > 0 && cnt <= r - l;
  }
  vector<int>ans;
  void play(vector<int>p, int l, int r){
    if(p.size() == 1){
      ans[p[0]] = l;
      return;
    }
    int d = 1;
    while(!check(l, r, d)){
      d++;
    }
    vector<int>left, right, b(n, 0);
    for(int& i : p){
      b[i] = d;
    }
    b = play_round(b);
    for(int& i : p){
      if(b[i] > d){
        right.push_back(i);
      }
      else{
        left.push_back(i);
      }
    }
    play(left, l, l + int(left.size()) - 1);
    play(right, l + left.size(), r);
  }
  vector<int>solve(){
    ans.resize(n);
    iota(ans.begin(), ans.end(), 0);
    play(ans, 1, n);
    return ans;
  }
}
void allValues(int _n, int _w, int *P){
  n = _n;
  vector<int>ans = (w = _w) == (n << 1) ? sub4::solve() : sub5::solve();
  for(int i = 0; i < n; i++){
    P[i] = ans[i];
  }
}

Compilation message (stderr)

koala.cpp: In function 'int sub3::solve()':
koala.cpp:89:3: warning: control reaches end of non-void function [-Wreturn-type]
   89 |   }
      |   ^

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 53 / 53