Submission #1175719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175719		Zero_OP	Ancient Machine (JOI21_ancient_machine)	C++20	0 / 100	63 ms	6432 KiB

Anna

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

using namespace std;

namespace{
#define sz(v) (int)v.size()

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.push_back(carry);
      while(!c.empty() && c.back() == 0) c.pop_back();
      return c;
}

bool is_greater_or_equal(const bigint& a, const bigint& b){
      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 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';
      }
}
}

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;
      }

      vector<bigint> fib(260);
      fib[0] = {1};
      fib[1] = {0, 1};

      for(int i = 2; i < (int)fib.size(); ++i){
            fib[i] = fib[i-2] + fib[i-1];
      }

      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;
            }
      }

      const int T = 250;
      const int B = 174;

      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];
                  }
            }

            sum.resize(174);

            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;


#define sz(v) (int)v.size()

namespace{
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.push_back(carry);
      while(!c.empty() && c.back() == 0) c.pop_back();
      return c;
}

bool is_greater_or_equal(const bigint& a, const bigint& b){
      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 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';
      }
}
}

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(260);
      fib[0] = {1};
      fib[1] = {0, 1};

      for(int i = 2; i < (int)fib.size(); ++i){
            fib[i] = fib[i-2] + fib[i-1];
      }

      const int T = 250;
      const int B = 174;
      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.push_back(A[i]);
            }

            for(int i = T; i >= 0; --i){
                  if(is_greater_or_equal(sum, fib[i])){
                        sum = sum - fib[i];
                        bit[i + (b * T)] = 1;
                  }
            }
      }

      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: 0 / 5
• Subtask 2: 0 / 95