Submission #1175893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175893		Zero_OP	Ancient Machine (JOI21_ancient_machine)	C++20	100 / 100	110 ms	6856 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
      #define sz(v) (int)v.size()
      #define pb push_back
      using bigint = vector<int>; //reversed order

      const int base = 2;
      bigint operator + (bigint a, bigint b){
            int n = max(sz(a), sz(b));
            a.resize(n);
            b.resize(n);
            bigint c(n);
            int carry = 0;
            for(int i = 0; i < n; ++i){
                  c[i] = a[i] + b[i] + carry;
                  if(c[i] >= base){
                        carry = 1;
                        c[i] -= base;
                  } else carry = 0;
            }
            if(carry) c.pb(carry);
            while(!c.empty() && c.back() == 0) c.pop_back();
            return c;
      }

      void show(const bigint& n){
            if(n.empty()){
                  cout << 0 << '\n';
            } else{
                  for(int i = sz(n)-1; i >= 0; --i) cout << n[i];
                  cout << '\n';
            }
      }
      
      bool is_greater_or_equal(const bigint& a, const bigint& b){
            cout << "comparison :\n";
            show(a);
            show(b);
            cout << '\n';
            if(sz(a) != sz(b)) return sz(a) > sz(b);
            for(int i = sz(a)-1; i >= 0; --i){
                  if(a[i] != b[i]) return a[i] > b[i];
            }
            return true; //equal
      }

      bigint operator - (bigint a, bigint b){ //assume that a >= b
            int n = max(sz(a), sz(b));
            a.resize(n); b.resize(n);
            int carry = 0;
            bigint c(n);
            for(int i = 0; i < n; ++i){
                  c[i] = a[i] - b[i] - carry;
                  if(c[i] < 0){
                        c[i] += base;
                        carry = 1;
                  } else carry = 0;
            }
            while(!c.empty() && c.back() == 0) c.pop_back();
            return c;
      }
}

void Anna(int N, vector<char> S){
      int f = -1;
      for(int i = 0; i < N; ++i){
            if(S[i] == 'X'){
                  f = i;
                  break;
            }
      }

      if(f == -1){
            Send(0);
            return;
      }

      int nf = f;
      while(nf + 1 < N && S[nf+1] == 'Z') ++nf;

      vector<bool> bit(N);
      bit[f] = true;

      for(int i = nf + 1; i < N; ++i){
            if(S[i] == 'Z') {
                  while(i+1 < N && S[i+1] == 'Z') ++i;
                  bit[i] = true;
            }
      }

      vector<bigint> fib(501);
      fib[0] = {1}, fib[1] = {0, 1}, fib[2] = {1, 1};
      for(int i = 3; i < sz(fib); ++i){
            fib[i] = fib[i-1] + fib[i-2];
      }

      const int T = 498;
      const int B = 348;

      // cout << "Anna Send : ";
      // for(int i = 0; i < N; ++i) cout << bit[i]; cout << '\n';

      for(int l = 0; l < N; l += T){
            int r = min(N, l + T);
            bigint sum;
            for(int i = l; i < r; ++i){
                  if(bit[i]){
                        sum = sum + fib[i - l];
                  }
            }

            assert(sz(sum) < B);
            sum.resize(B);

            // show(sum);

            for(int i = 0; i < B; ++i){
                  Send(sum[i]);
            }
      }

      if(nf == f){
            for(int i = 0; i < 17; ++i) Send(1);
      } else{
            for(int i = 0; i < 17; ++i) Send(nf >> i & 1);
      }
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
      #define sz(v) (int)v.size()
      #define pb push_back
      #define dbg(x) "[" #x " = " << (x) << "]"
      using bigint = vector<short>; //reversed order

      const int base = 2;
      bigint operator + (bigint a, bigint b){
            int n = max(sz(a), sz(b));
            a.resize(n);
            b.resize(n);
            bigint c(n);
            int carry = 0;
            for(int i = 0; i < n; ++i){
                  c[i] = a[i] + b[i] + carry;
                  if(c[i] >= base){
                        carry = 1;
                        c[i] -= base;
                  } else carry = 0;
            }
            if(carry) c.pb(carry);
            while(!c.empty() && c.back() == 0) c.pop_back();
            return c;
      }

      void show(const bigint& n){
            if(n.empty()){
                  cout << 0 << '\n';
            } else{
                  for(int i = sz(n)-1; i >= 0; --i) cout << n[i];
                  cout << '\n';
            }
      }
      
      bool is_greater_or_equal(const bigint& a, const bigint& b){
            // cout << "comparison :\n";
            // show(a);
            // show(b);
            // cout << '\n';
            // cout << sz(a) << ' ' << sz(b) << '\n';
            if(sz(a) != sz(b)) return sz(a) > sz(b);
            for(int i = sz(a)-1; i >= 0; --i){
                  // cout << dbg(i) << dbg(a[i]) << dbg(b[i]) << '\n';
                  if(a[i] != b[i]) {
                        // cout << dbg(i) << dbg(a[i]) << dbg(b[i]) << '\n';
                        return a[i] > b[i];
                  }
            }
            return true; //equal
      }

      bigint operator - (bigint a, bigint b){ //assume that a >= b
            int n = max(sz(a), sz(b));
            a.resize(n); b.resize(n);
            int carry = 0;
            bigint c(n);
            for(int i = 0; i < n; ++i){
                  c[i] = a[i] - b[i] - carry;
                  if(c[i] < 0){
                        c[i] += base;
                        carry = 1;
                  } else carry = 0;
            }
            return c;
      }
}

void Bruno(int N, int L, vector<int> A){
      if(L == 1){
            for(int i = 0; i < N; ++i) Remove(i);
            return;
      }

      vector<bigint> fib(501);
      fib[0] = {1}, fib[1] = {0, 1}, fib[2] = {1, 1};
      for(int i = 3; i < sz(fib); ++i){
            fib[i] = fib[i-1] + fib[i-2];
      }

      const int T = 498;
      const int B = 348;

      for(int i = 0; i < sz(fib); ++i) fib[i].resize(B);
      int nBlocks = L / B;

      vector<bool> bit(N);

      for(int b = 0; b < nBlocks; ++b){
            int l = b * B, r = (b + 1) * B;
            
            bigint sum;
            for(int i = l; i < r; ++i){
                  sum.pb(A[i]);
            }

            // show(sum);

            for(int i = T; i >= 0; --i){
                  // show(sum);
                  // show(fib[i]);
                  // bool x = is_greater_or_equal(sum, fib[i]);
                  // cout << dbg(x) << '\n';

                  if(is_greater_or_equal(sum, fib[i])){
                        // return;
                        sum = sum - fib[i];
                        assert(sz(sum) == B);
                        bit[i + (b * T)] = 1;
                  }
            }
      }

      // cout << "Bruno Receive :";
      // for(int i = 0; i < N; ++i) cout << bit[i]; cout << '\n';

      int extra = 0;
      for(int i = 0; i < 17; ++i){
            if(A[i + nBlocks * B]) extra |= (1 << i);
      }

      int f = -1;
      for(int i = 0; i < N; ++i){
            if(bit[i]){
                  f = i;
                  break;
            }
      }

      int s = -1;
      for(int i = N - 1; i >= 0; --i){
            if(bit[i]){
                  s = i;
                  break;
            }
      }

      vector<int> result;
      for(int i = 0; i < f; ++i) result.push_back(i);
      for(int i = N-1; i > s; --i) result.push_back(i);

      int old = -1;
      if(extra < N){
            old = f;
            f = extra;
            for(int i = old + 1; i <= f; ++i) result.push_back(i);
      } 

      int last = f;
      for(int i = f + 1; i <= s; ++i){
            if(bit[i]){
                  for(int j = i-1; j > last; --j) result.push_back(j);
                  result.push_back(i);
                  last = i; 
            }
      }

      if(old != -1) result.push_back(old);
      else result.push_back(f);

      for(int i = 0; i < N; ++i) Remove(result[i]);
}

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