Submission #1133182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133182		huutuan	Ancient Machine (JOI21_ancient_machine)	C++20	100 / 100	1262 ms	9220 KiB

Anna

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

#include <bits/stdc++.h>

using namespace std;

namespace Anna_solver{
   struct Bignum{
      vector<unsigned long long> val;
      Bignum operator+(const Bignum &_) const {
         auto a=val, b=_.val;
         Bignum c;
         c.val.resize(max(a.size(), b.size()));
         reverse(a.begin(), a.end());
         reverse(b.begin(), b.end());
         unsigned long long carry=0, new_carry=0;
         for (int i=0; i<(int)c.val.size(); ++i){
            unsigned long long A=i<(int)a.size()?a[i]:0;
            unsigned long long B=i<(int)b.size()?b[i]:0;
            if (A>ULLONG_MAX-B || (A==ULLONG_MAX-B && carry)) new_carry=1;
            else new_carry=0;
            c.val[i]=A+B+carry;
            carry=new_carry;
         }
         if (carry) c.val.push_back(1);
         reverse(c.val.begin(), c.val.end());
         return c;
      }
   };
   const int M=1e5+10;
   // Bignum fib[M];
   void solve(int N, vector<char> S){
      // fib[0].val={1};
      // fib[1].val={2};
      // for (int i=2; i<M; ++i){
      //    fib[i]=fib[i-1]+fib[i-2];
      // }
      int i=0;
      while (i<N && S[i]!='X') ++i;
      vector<int> v(N);
      Bignum sum;
      if (i<N){
         v[i]=1;
         for (int j=i+2; j<N; ++j) if (S[j]=='Z'){
            int k=j;
            while (k+1<N && S[k+1]=='Z') ++k;
            v[k]=1;
            j=k;
         }
         if (i+1<N && S[i+1]=='Z' && (i+2>=N || S[i+2]!='Z')) Send(1), Send(0);
         else Send(0), Send(0); 
      }
      // for (int i=0; i<N; ++i) if (v[i]) sum=sum+fib[i];
      Bignum a, b;
      a.val={1}, b.val={2};
      if (v[0]) sum=sum+a;
      if (v[1]) sum=sum+b;
      for (int i=2; i<N; ++i){
         tie(a, b)=make_pair(b, a+b);
         if (v[i]) sum=sum+b;
      }
      for (int i=0; i<(int)sum.val.size(); ++i){
         for (int t=63; t>=0; --t) Send(sum.val[i]>>t&1);
      }
   }
}

void Anna(int N, std::vector<char> S) {
   Anna_solver::solve(N, S);
}

Bruno

#include "Bruno.h"
#include <vector>

#include <bits/stdc++.h>

using namespace std;

namespace Bruno_solver{
   struct Bignum{
      vector<unsigned long long> val;
      Bignum operator+(const Bignum &_) const {
         auto a=val, b=_.val;
         Bignum c;
         c.val.resize(max(a.size(), b.size()));
         reverse(a.begin(), a.end());
         reverse(b.begin(), b.end());
         unsigned long long carry=0, new_carry=0;
         for (int i=0; i<(int)c.val.size(); ++i){
            unsigned long long A=i<(int)a.size()?a[i]:0;
            unsigned long long B=i<(int)b.size()?b[i]:0;
            if (A>ULLONG_MAX-B || (A==ULLONG_MAX-B && carry)) new_carry=1;
            else new_carry=0;
            c.val[i]=A+B+carry;
            carry=new_carry;
         }
         if (carry) c.val.push_back(1);
         reverse(c.val.begin(), c.val.end());
         return c;
      }
      Bignum operator-(const Bignum &_) const {
         auto a=val, b=_.val;
         Bignum c;
         c.val.resize(max(a.size(), b.size()));
         reverse(a.begin(), a.end());
         reverse(b.begin(), b.end());
         unsigned long long carry=0, new_carry=0;
         for (int i=0; i<(int)c.val.size(); ++i){
            unsigned long long A=i<(int)a.size()?a[i]:0;
            unsigned long long B=i<(int)b.size()?b[i]:0;
            if (A<B || (A==B && carry)) new_carry=1;
            else new_carry=0;
            c.val[i]=A-B-carry;
            carry=new_carry;
         }
         assert(!carry);
         while (c.val.back()==0 && (int)c.val.size()>1) c.val.pop_back();
         reverse(c.val.begin(), c.val.end());
         return c;
      }
      bool operator>=(const Bignum &a) const {
         if (val.size()!=a.val.size()) return val.size()>a.val.size();
         for (int i=0; i<(int)val.size(); ++i) if (val[i]!=a.val[i]) return val[i]>a.val[i];
         return 1;
      }
   };
   const int M=1e5+10;
   Bignum fib[M];
   void solve(int N, int L, vector<int> B){
      if (B.empty()){
         for (int i=0; i<N; ++i) Remove(i);
         return;
      }
      bool check=B[0];
      B.erase(B.begin(), B.begin()+2);
      vector<int> A(N);
      Bignum sum;
      while ((int)B.size()%64) B.insert(B.begin(), 0);
      for (int l=0, r=63; r<B.size(); l+=64, r+=64){
         sum.val.emplace_back();
         for (int j=l; j<=r; ++j) sum.val.back()=sum.val.back()<<1|B[j];
      }
      Bignum a, b;
      a.val={1}; b.val={2};
      for (int i=2; i<N; ++i){
         tie(a, b)=make_pair(b, a+b);
      }
      for (int i=N-1; i>=0; --i){
         if (sum>=b){
            sum=sum-b;
            A[i]=1;
            // cout << i << ' ';
         }
         tie(a, b)=make_pair(b-a, a);
      }
      int x=find(A.begin(), A.end(), 1)-A.begin();
      for (int i=0; i<x; ++i) Remove(i);
      int j=x+1;
      if (check) A[j]=1;
      for (int i=x+1; i<N; ++i) if (A[i]==1){
         for (int k=i-1; k>=j; --k) Remove(k);
         Remove(i);
         j=i+1;
      }
      for (int i=j; i<N; ++i) Remove(i);
      Remove(x);
   }
}  // namespace

void Bruno(int N, int L, std::vector<int> A) {
   Bruno_solver::solve(N, L, A);
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95