Submission #1138087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138087		huutuan	Broken Device 2 (JOI22_device2)	C++20	76 / 100	295 ms	3396 KiB

Anna

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

#include <bits/stdc++.h>

using namespace std;

namespace Anna_solver{
   const int M=280, BIT=60;
   int Declare(){
      return M;
   }
   mt19937 rng(69420);
   pair<vector<int>, vector<int>> Anna(long long A){
      long long val=uniform_int_distribution<long long>(0, (1ll<<BIT)-1)(rng);
      // long long val=0;
      A^=val;
      vector<int> v;
      for (int i=0; i<BIT; ++i){
         v.push_back(i&1);
         v.push_back(i&1);
         v.push_back(i&1);
         if (A>>i&1){
            // v.push_back(i&1);
            v.push_back(i&1);
            v.push_back(i&1);
         }
      }
      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=280, BIT=60;
   mt19937 rng(69420);
   const int L0=3, L1=5;
   // long long f[M*2+1][BIT+1][BIT+1][2][L1+1];
   // vector<int> tr[M*2+1][BIT+1][BIT+1][2][L1+1];
   int n;
   long long Bruno(vector<int> v){
      n=v.size();
      long long val=uniform_int_distribution<long long>(0, (1ll<<BIT)-1)(rng);
      // long long val=0;
      long long ans=-1;
      int _b1=(n/2-L0*BIT)/(L1-L0), _b0=BIT-_b1;
      assert(_b0*L0+_b1*L1==n/2);
      // memset(f, -1, sizeof f);
      // f[0][0][0][0][0]=0;
      // int cnt=0;
      // for (int i=0; i<n; ++i){
      //    for (int b0=0; b0<=BIT; ++b0){
      //       for (int b1=0; b1<=BIT; ++b1){
      //          for (int k=0; k<2; ++k) for (int l=0; l<L1; ++l) if (f[i][b0][b1][k][l]!=-1){
      //             ++cnt;
      //             auto transition=[&](long long &x, long long y, vector<int> &tx, vector<int> &ty){
      //                if (x!=-1 && x!=y){
      //                   for (int t=0; t<=i; ++t){
      //                      if (find(tx.begin(), tx.end(), t)!=tx.end()) cout << '?';
      //                      else cout << v[t];
      //                   }
      //                   cout << '\n';
      //                   for (int t=0; t<=i; ++t){
      //                      if (find(ty.begin(), ty.end(), t)!=ty.end()) cout << '?';
      //                      else cout << v[t];
      //                   }
      //                   cout << '\n';
      //                   exit(0);
      //                }
      //                assert(x==-1 || x==y);
      //                x=y;
      //                tx=ty;
      //             };
      //             if (v[i]==((i-b0*L0-b1*L1-l)&1)){
      //                transition(f[i+1][b0][b1][k][l], f[i][b0][b1][k][l], tr[i+1][b0][b1][k][l], tr[i][b0][b1][k][l]);
      //                // tr[i+1][b0][b1][k][l].push_back(i);
      //             }
      //             if (v[i]==k && l<L1){
      //                transition(f[i+1][b0][b1][k][l+1], f[i][b0][b1][k][l], tr[i+1][b0][b1][k][l+1], tr[i][b0][b1][k][l]);
      //                if (l+1==L0 && b0<BIT){
      //                   transition(f[i+1][b0+1][b1][k^1][0], f[i][b0][b1][k][l], tr[i+1][b0+1][b1][k^1][0], tr[i][b0][b1][k][l]);
      //                }
      //                if (l+1==L1 && b1<BIT){
      //                   transition(f[i+1][b0][b1+1][k^1][0], f[i][b0][b1][k][l]|(1ll<<(b0+b1)), tr[i+1][b0][b1+1][k^1][0], tr[i][b0][b1][k][l]);
      //                }
      //             }
      //          }
      //       }
      //    }
      // }
      // cerr << cnt << endl;
      map<array<int, 5>, long long> f;
      priority_queue<array<int, 5>, vector<array<int, 5>>, greater<array<int, 5>>> q;
      q.push({0, 0, 0, 0, 0});
      f[{0, 0, 0, 0, 0}]=0;
      while (q.size()){
         long long ff=f[q.top()];
         int i=q.top()[0], b0=q.top()[1], b1=q.top()[2], k=q.top()[3], l=q.top()[4]; q.pop();
         // assert(ff==f[i][b0][b1][k][l]);
         if (i<n && b0<=BIT && b1<=BIT && k<2 && l<L1){
            if (v[i]==((i-b0*L0-b1*L1-l)&1)){
               if (!f.count({i+1, b0, b1, k, l})) f[{i+1, b0, b1, k, l}]=ff, q.push({i+1, b0, b1, k, l});
            }
            if (v[i]==k && l<L1){
               if (!f.count({i+1, b0, b1, k, l+1})) f[{i+1, b0, b1, k, l+1}]=ff, q.push({i+1, b0, b1, k, l+1});
               if (l+1==L0 && b0<BIT){
                  if (!f.count({i+1, b0+1, b1, k^1, 0})) f[{i+1, b0+1, b1, k^1, 0}]=ff, q.push({i+1, b0+1, b1, k^1, 0});
               }
               if (l+1==L1 && b1<BIT){
                  if (!f.count({i+1, b0, b1+1, k^1, 0})) f[{i+1, b0, b1+1, k^1, 0}]=ff|(1ll<<(b0+b1)), q.push({i+1, b0, b1+1, k^1, 0});
               }
            }
         }
      }
      assert(f.count({n, _b0, _b1, 0, 0}));
      ans=f[{n, _b0, _b1, 0, 0}];
      cerr << f.size() << endl;
      // ans=f[n][_b0][_b1][0][0];
      assert(ans!=-1);
      return ans^val;
   }
}

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