Submission #1139376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139376		huutuan	Broken Device 2 (JOI22_device2)	C++20	92 / 100	184 ms	2180 KiB

Anna

#include "Anna.h"
#include <utility>
#include <vector>

#include <bits/stdc++.h>

using namespace std;

namespace Anna_solver{
   const int M=149, BIT=60, MX=21;
   int Declare(){
      return M;
   }
   long long dp[M+10];
   void gen(){
      dp[0]=1;
      for (int i=0; i<=M; ++i){
         for (int k=3; k<=MX; k+=2) if (i+k<=M) dp[i+k]+=dp[i];
      }
   }
   pair<vector<int>, vector<int>> Anna(long long A){
      if (!dp[0]) gen();
      int len=0;
      while (A>=dp[len]){
         A-=dp[len];
         ++len;
      }
      vector<int> v;
      while ((int)v.size()<len){
         for (int k=3; k<=MX; k+=2){
            if (A>=dp[len-(int)v.size()-k]){
               A-=dp[len-(int)v.size()-k];
            }else{
               int val=v.empty()?0:(v.back()^1);
               while (k--) v.push_back(val);
               break;
            }
         }
      }
      vector<int> vv;
      for (int i=0; i<(int)v.size(); ++i) vv.push_back(i&1);
      return {v, vv};
   }
}

int Declare() {
   return Anna_solver::Declare();
}

std::pair<std::vector<int>, std::vector<int> > Anna(long long A) {
   return Anna_solver::Anna(A);
}

Bruno

#include "Bruno.h"
#include <utility>
#include <vector>

#include <bits/stdc++.h>

using namespace std;

namespace Bruno_solver{
   const int M=149, BIT=60;
   const int MX=21;
   int n;
   long long dp[M+10];
   void gen(){
      dp[0]=1;
      for (int i=0; i<=M; ++i){
         for (int k=3; k<=MX; k+=2) if (i+k<=M) dp[i+k]+=dp[i];
      }
   }
   long long Bruno(vector<int> v){
      if (!dp[0]) gen();
      n=v.size();
      int len=n/2;
      long long ans=-1;
      map<array<int, 4>, pair<long long, int>> mp;
      priority_queue<array<int, 4>, vector<array<int, 4>>, greater<array<int, 4>>> q;
      q.push({0, 0, 0, 0});
      mp[{0, 0, 0, 0}]={0, 0};
      while (q.size()){
         auto ff=mp[q.top()];
         int i=q.top()[0], j=q.top()[1], k=q.top()[2], l=q.top()[3]; q.pop();
         if (i<n && j<=n/2 && k<2 && l<MX){
            if (v[i]==(j&1) && j<n/2){
               if (!mp.count({i+1, j+1, k, l})) mp[{i+1, j+1, k, l}]=ff, q.push({i+1, j+1, k, l});
            }
            if (v[i]==k && l+1<=MX){
               if (l+1<MX){
                  if (!mp.count({i+1, j, k, l+1})) mp[{i+1, j, k, l+1}]=ff, q.push({i+1, j, k, l+1});
               }
               if ((l+1)&1 && l>=2){
                  auto g=ff;
                  g.second+=l+1;
                  for (int k=3; k<l+1; k+=2) g.first+=dp[len-ff.second-k];
                  if (!mp.count({i+1, j, k^1, 0})) mp[{i+1, j, k^1, 0}]=g, q.push({i+1, j, k^1, 0});
               }
            }
         }
      }
      assert(mp.count({n, n/2, 0, 0})+mp.count({n, n/2, 1, 0})==1);
      if (mp.count({n, n/2, 0, 0})) ans=mp[{n, n/2, 0, 0}].first;
      else ans=mp[{n, n/2, 1, 0}].first;
      for (int i=0; i<len; ++i) ans+=dp[i];
      return ans;
   }
}

long long Bruno(std::vector<int> u) {
   return Bruno_solver::Bruno(u);
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 3 / 3
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 52 / 60