Submission #1139599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139599		huutuan	Broken Device 2 (JOI22_device2)	C++20	60 / 100	2008 ms	2504 KiB

Anna

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

#include <bits/stdc++.h>

using namespace std;

namespace Anna_solver{
   const int M=140, 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=i==0?1: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();
      long long h=5e17;
      int rev=0;
      if (A>=h){
         A-=h;
         rev=1;
      }
      int len=1;
      while (A>=dp[len]*(141-len)){
         A-=dp[len]*(141-len);
         ++len;
      }
      int real_len=len;
      while (A>=dp[len]){
         A-=dp[len];
         ++real_len;
      }
      vector<int> v;
      while ((int)v.size()<len){
         for (int k=(len-v.size())==1?1: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;
            }
         }
      }
      reverse(v.begin(), v.end());
      while ((int)v.size()<real_len) v.push_back(v.back()^1);
      reverse(v.begin(), v.end());
      if (v[0]) for (int &i:v) i^=1;
      vector<int> vv;
      for (int i=0; i<(int)v.size(); ++i) vv.push_back(vv.empty()?0:vv.back()^1);
      if (rev){
         for (int &i:v) i^=1;
         for (int &i:vv) 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=140, 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=i==0?1:3; k<=MX; k+=2) if (i+k<=M) dp[i+k]+=dp[i];
      }
   }
   long long Bruno(vector<int> v){
      if (!dp[0]) gen();
      long long h=5e17;
      int rev=0;
      if (v[0]==1){
         rev=1;
         for (int &i:v) i^=1;
      }
      n=v.size();
      int len=n/2;
      long long ans=-1;
      map<array<int, 5>, pair<long long, int>> mp;
      priority_queue<array<int, 5>, vector<array<int, 5>>, greater<array<int, 5>>> q;
      q.push({0, 0, 0, 0, 0});
      mp[{0, 0, 0, 0, 0}]={h*rev, 0};
      while (q.size()){
         auto ff=mp[q.top()];
         auto transition=[&](array<int, 5> id, pair<long long, int> val){
            int i=id[0], j=id[1], k=id[2], l=id[3], m=id[4];
            if (i<=n && j<=n/2 && k<2 && l<MX && m<2 && i-j<=n/2){
               if (mp.count(id)) assert(mp[id]==val);
               else q.push(id);
               assert(val.second>=0);
               mp[id]=val;
            }
         };
         int i=q.top()[0], j=q.top()[1], k=q.top()[2], l=q.top()[3], m=q.top()[4]; q.pop();
         if (v[i]==(j&1) && j<n/2){
            transition({i+1, j+1, k, l, m}, ff);
         }
         if (v[i]==k && l+1<=MX){
            if (l+1<MX){
               transition({i+1, j, k, l+1, m}, ff);
            }
            if ((l+1)&1){
               if (j+(n-i-1)==n/2){
                  if (m==0){
                     int add=i-j-l;
                     int len=n/2-add;
                     auto g=ff;
                     g.first+=dp[len]*add;
                     for (int i=1; i<len; ++i) g.first+=dp[i]*(141-i);
                     g.second=len-l-1;
                     for (int k=3; k<l+1; k+=2) g.first+=dp[len-k];
                     transition({i+1, j, k^1, 0, 1}, g);
                  }else{
                     auto g=ff;
                     g.second-=l+1;
                     for (int k=3; k<l+1; k+=2) g.first+=dp[ff.second-k];
                     transition({i+1, j, k^1, 0, 1}, g);
                  }
               }else if (l==0){
                  if (m==0){
                     auto g=ff;
                     transition({i+1, j, k^1, 0, 0}, g);
                  }
               }else{
                  if (m==0){
                     int add=i-j-l;
                     int len=n/2-add;
                     auto g=ff;
                     g.first+=dp[len]*add;
                     for (int i=1; i<len; ++i) g.first+=dp[i]*(141-i);
                     g.second=len-l-1;
                     for (int k=3; k<l+1; k+=2) g.first+=dp[len-k];
                     transition({i+1, j, k^1, 0, 1}, g);
                  }else{
                     auto g=ff;
                     g.second-=l+1;
                     for (int k=3; k<l+1; k+=2) g.first+=dp[ff.second-k];
                     transition({i+1, j, k^1, 0, 1}, g);
                  }
               }
            }
         }
      }
      if (mp.count({n, n/2, 0, 0, 1})){
         ans=mp[{n, n/2, 0, 0, 1}].first;
      }
      if (mp.count({n, n/2, 1, 0, 1})){
         ans=mp[{n, n/2, 1, 0, 1}].first;
      }
      // cerr << mp.size() << '\n';
      return ans;
   }
}

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

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