Submission #1139528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139528		huutuan	Broken Device 2 (JOI22_device2)	C++20	96 / 100	261 ms	2120 KiB

Anna

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

#include <bits/stdc++.h>

using namespace std;

namespace Anna_solver{
   const int M=144, BIT=60, MX=21;
   int Declare(){
      return M;
   }
   long long dp[M+10], dp2[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];
      }
      dp2[0]=1;
      for (int i=0; i<=M; ++i){
         if (!i){
            for (int k=2; k<=MX; k+=2) if (i+k<=M) dp2[i+k]+=dp2[i];
         }else{
            for (int k=3; k<=MX; k+=2) if (i+k<=M) dp2[i+k]+=dp2[i];
         }
      }
      for (int i=2; i<=M; ++i){
         long long sum=0;
         for (int k=2; k<=MX; k+=2) if (i>=k) sum+=dp[i-k];
         assert(dp2[i]==sum);
      }
   }
   pair<vector<int>, vector<int>> Anna(long long A){
      if (!dp[0]) gen();
      long long l1=51e16, l2=68e16;
      int s1=0;
      int k0=3;
      int len=0;
      if (A<=l1){
         if (A>l1/2) s1=1, A-=l1/2;
         while (A>=dp[len]){
            A-=dp[len];
            ++len;
         }
      }else{
         k0=2;
         A-=l1;
         if (A>l2/2) s1=1, A-=l2/2;
         while (A>=dp2[len]){
            A-=dp2[len];
            ++len;
         }
      }
      vector<int> v;
      while ((int)v.size()<len){
         for (int k=v.empty()?k0: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()?s1:(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(vv.empty()?0:vv.back()^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=144, BIT=60;
   const int MX=21;
   int n;
   long long dp[M+10], dp2[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];
      }
      dp2[0]=1;
      for (int i=0; i<=M; ++i){
         if (!i){
            for (int k=2; k<=MX; k+=2) if (i+k<=M) dp2[i+k]+=dp2[i];
         }else{
            for (int k=3; k<=MX; k+=2) if (i+k<=M) dp2[i+k]+=dp2[i];
         }
      }
   }
   long long Bruno(vector<int> v){
      long long l1=51e16, l2=68e16;
      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};
      q.push({0, 0, 1, 0});
      mp[{0, 0, 1, 0}]={l1/2, 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();
         auto transition=[&](array<int, 4> id, pair<long long, int> val){
            if (mp.count(id)) assert(mp[id]==val);
            else q.push(id);
            mp[id]=val;
         };
         if (i<n && j<=n/2 && k<2 && l<MX){
            if (v[i]==(j&1) && j<n/2){
               transition({i+1, j+1, k, l}, ff);
            }
            if (v[i]==k && l+1<=MX){
               if (l+1<MX){
                  transition({i+1, j, k, l+1}, ff);
               }
               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];
                  transition({i+1, j, k^1, 0}, g);
               }
            }
         }
      }
      if (mp.count({n, n/2, 0, 0})){
         ans=mp[{n, n/2, 0, 0}].first;
         for (int i=0; i<len; ++i) ans+=dp[i];
      }
      if (mp.count({n, n/2, 1, 0})){
         ans=mp[{n, n/2, 1, 0}].first;
         for (int i=0; i<len; ++i) ans+=dp[i];
      }
      mp.clear();
      q.push({0, 0, 0, 0});
      mp[{0, 0, 0, 0}]={l1, 0};
      q.push({0, 0, 1, 0});
      mp[{0, 0, 1, 0}]={l1+l2/2, 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();
         auto transition=[&](array<int, 4> id, pair<long long, int> val){
            if (mp.count(id)) assert(mp[id]==val);
            else q.push(id);
            mp[id]=val;
         };
         if (i<n && j<=n/2 && k<2 && l<MX){
            if (v[i]==(j&1) && j<n/2){
               transition({i+1, j+1, k, l}, ff);
            }
            if (v[i]==k && l+1<=MX){
               if (l+1<MX){
                  transition({i+1, j, k, l+1}, ff);
               }
               if (i==l+j){
                  if (l&1){
                     auto g=ff;
                     g.second+=l+1;
                     for (int k=2; k<l+1; k+=2) g.first+=dp[len-ff.second-k];
                     transition({i+1, j, k^1, 0}, g);
                  }
               }else 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];
                  transition({i+1, j, k^1, 0}, g);
               }
            }
         }
      }
      if (mp.count({n, n/2, 0, 0})){
         ans=mp[{n, n/2, 0, 0}].first;
         for (int i=0; i<len; ++i) ans+=dp2[i];
      }
      if (mp.count({n, n/2, 1, 0})){
         ans=mp[{n, n/2, 1, 0}].first;
         for (int i=0; i<len; ++i) ans+=dp2[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: 56 / 60