Submission #1175662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175662		Zero_OP	Ancient Machine (JOI21_ancient_machine)	C++20	96 / 100	39 ms	6408 KiB

Anna

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

using namespace std;

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<unsigned long long> fib(100);
      fib[0] = 1, fib[1] = 2, fib[2] = 3;
      for(int i = 3; i < 100; ++i){
            fib[i] = fib[i-1] + fib[i-2];
      }

      const int T = 88;
      const int B = 63;

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

            for(int i = 0; i < 63; ++i){
                  Send(sum >> i & 1);
            }
      }

      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;

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

      vector<unsigned long long> fib(100);
      fib[0] = 1, fib[1] = 2, fib[2] = 3;
      for(int i = 3; i < 100; ++i) fib[i] = fib[i-2] + fib[i-1];

      const int T = 88;
      const int B = 63;
      int nBlocks = L / B;

      vector<bool> bit(N);

      for(int b = 0; b < nBlocks; ++b){
            int l = b * B, r = (b + 1) * B;
            
            long long sum = 0;
            for(int i = l; i < r; ++i){
                  if(A[i]){
                        sum += (1LL << (i - l));
                  }
            }

            for(int i = 88; i >= 0; --i){
                  if(sum >= fib[i]){
                        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: 5 / 5
• Subtask 2: 91 / 95