Submission #1139609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139609		huutuan	Broken Device 2 (JOI22_device2)	C++20	100 / 100	644 ms	2120 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];
      }
   }
   mt19937 rng(69420);
   pair<vector<int>, vector<int>> Anna(long long A){
      long long inf=1e18;
      long long val=uniform_int_distribution<long long>(0, inf)(rng);
      A=(A+val)%(inf+1);
      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];
   long long pf1[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];
      }
      for (int i=1; i<=M; ++i){
         pf1[i]=pf1[i-1]+dp[i]*(141-i);
      }
   }
   mt19937 rng(69420);
   long long Bruno(vector<int> v){
      long long inf=1e18;
      long long val=uniform_int_distribution<long long>(0, inf)(rng);
      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<int, pair<long long, int>> mp;
      priority_queue<int, vector<int>, greater<int>> q;
      q.push(0);
      mp[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];
            int hs=((((i*(M+1)+j)*2+k)*MX+l)*2+m);
            if (i<=n && j<=n/2 && k<2 && l<MX && m<2 && i-j<=n/2){
               if (mp.count(hs)) assert(mp[hs]==val);
               else q.push(hs);
               assert(val.second>=0);
               mp[hs]=val;
            }
         };
         int hs=q.top(); q.pop();
         int i, j, k, l, m;
         m=hs%2, hs/=2;
         l=hs%MX; hs/=MX;
         k=hs%2, hs/=2;
         j=hs%(M+1); hs/=M+1;
         i=hs;
         // 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;
                     g.first+=pf1[len-1];
                     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;
                     g.first+=pf1[len-1];
                     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);
                  }
               }
            }
         }
      }
      int hs=((((n*(M+1)+n/2)*2+0)*MX+0)*2+1);
      if (mp.count(hs)){
         ans=mp[hs].first;
      }
      if (mp.count(hs+MX*2)){
         ans=mp[hs+MX*2].first;
      }
      // cerr << mp.size() << '\n';
      ans=(ans+inf+1-val)%(inf+1);
      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: 60 / 60