Submission #1137811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137811		huutuan	Broken Device 2 (JOI22_device2)	C++20	0 / 100	241 ms	11884 KiB

Anna

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

#include <bits/stdc++.h>

using namespace std;

namespace Anna_solver{
   const int M=2000, L1=15, L0=15;
   vector<int> v[64];
   int Declare(){
      return M;
   }
   mt19937 rng(69420);
   void gen(){
      if (v[0].size()) return;
      for (int i=0; i<64; ++i){
         v[i]=vector<int>(L1+L0);
         fill(v[i].begin(), v[i].begin()+L1, 1);
         shuffle(v[i].begin()+1, v[i].end(), rng);
      }
   }
   pair<vector<int>, vector<int>> Anna(unsigned long long A){
      gen();
      unsigned long long val=uniform_int_distribution<unsigned long long>(0, ULLONG_MAX)(rng);
      A^=val;
      vector<int> vv;
      for (int i=0; i<64; ++i) if (A>>i&1) vv.insert(vv.end(), v[i].begin(), v[i].end());
      return {vv, vector<int>(vv.size(), 0)};
   }
}

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=2000, L1=15, L0=15;
   vector<int> v[64];
   mt19937 rng(69420);
   void gen(){
      if (v[0].size()) return;
      for (int i=0; i<64; ++i){
         v[i]=vector<int>(L1+L0);
         fill(v[i].begin(), v[i].begin()+L1, 1);
         shuffle(v[i].begin()+1, v[i].end(), rng);
      }
   }
   bool match(vector<int> va, vector<int> vb){
      int id=0;
      for (int i:vb) if (id<(int)va.size() && i==va[id]) ++id;
      return id==(int)va.size();
   }
   long long Bruno(vector<int> vv){
      gen();
      unsigned long long val=uniform_int_distribution<unsigned long long>(0, ULLONG_MAX)(rng);
      unsigned long long ans=0;
      int id=0, i=0;
      while (id<(int)vv.size()){
         vector<int> u;
         int cnt1=0;
         while (cnt1<L1){
            u.push_back(vv[id]);
            cnt1+=vv[id];
            ++id;
         }
         while (id<(int)vv.size() && !vv[id]) ++id, u.push_back(0);
         while (i<64 && !match(v[i], u)) ++i;
         if (i<64) ans|=1ull<<i;
      }
      return ans^val;
   }
}

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: 0 / 60