Submission #1175640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175640		Zero_OP	Ancient Machine (JOI21_ancient_machine)	C++20	0 / 100	5 ms	584 KiB

Anna

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

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vc = vector<char>;
using vb = vector<bool>;

/*
[fib[T+2] = 1293530146158671551]
[T = 90]
[bits = 62]
[cost = 67832]
*/

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

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

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

      vb target(N);
      target[f] = true;
      FOR(i, nf+1, N){
            if(S[i] == 'Z'){
                  target[i] = true;
                  while(i + 1 < N && S[i+1] == 'Z') ++i;
            }
      }

      vl fib(100);
      fib[0] = 1, fib[1] = 2, fib[2] = 3;
      FOR(i, 3, 91) fib[i] = fib[i-2] + fib[i-1];

      //check again if there is a 11 
      
      FOR(i, 1, N){
            if(target[i-1] && target[i]){
                  cout << "Failed Transmittion\n";
                  return;
            }
      }
      
      // cout << "Anna Send : \n";
      // FOR(i, 0, N) cout << target[i] << ' '; cout << '\n';

      for(int l = 0; l < N; l += 90){
            int r = min(N, l + 90);
            
            ll sum = 0;
            FOR(i, l, r){
                  if(target[i]) sum += fib[i - l];
            }

            // cout << "send : " << dbg(sum) << '\n';

            assert(sum < (1LL << 62));
            FOR(i, 0, 62){
                  Send(sum >> i & 1);
            }

            ll re = 0;
            FOR(i, 0, 62){
                  if(sum >> i & 1) re += (1LL << i);
                  // cout << re << '\n';
            }

            assert(re == sum);
            // cout << '\n';
      }

      if(nf != f){
            FOR(i, 0, 17) Send(nf >> i & 1); 
      } else{
            FOR(i, 0, 17) Send(1); //assume that if nf > N <=> no Z next to the first X from the right
      }
}

Bruno

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

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vc = vector<char>;
using vb = vector<bool>;

/*
[fib[T+2] = 1293530146158671551]
[T = 90]
[bits = 62]
[cost = 67832]
*/

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void Bruno(int N, int L, std::vector<int> A) {
      if(L == 1){
            FOR(i, 0, N){
                  Remove(i);
            }
            return;
      }

      vb target(N);

      vl fib(100);
      
      fib[0] = 1, fib[1] = 2, fib[2] = 3;
      FOR(i, 3, 91) fib[i] = fib[i-1] + fib[i-2];

      int nBlocks = L / 62;
      FOR(i, 0, nBlocks){
            int l = i * 62, r = (i+1) * 62;
            int lo = i * 90;

            ll sum = 0;
            FOR(i, l, r){
                  if(A[i]) {
                        sum += (1LL << (i - l)); 
                        // cout << dbg(sum) << '\n';
                  }           
            }
            // cout << '\n';

            // cout << "receive: " << dbg(sum) << '\n';

            for(int i = 90; i >= 0; --i){
                  if(sum >= fib[i]){
                        sum -= fib[i];
                        target[i + lo] = true;
                  }
            }
      }

      // cout << "Bruno Receive : \n";
      // FOR(i, 0, N) cout << target[i] << ' '; cout << '\n';

      int tmp = nBlocks * 62, pos = 0;
      FOR(i, 0, 17){
            if(A[i + tmp]) pos |= (1 << i);
      }

      int fst = -1, lst = -1;
      FOR(i, 0, N){
            if(target[i] && fst == -1){
                  fst = i;
            }

            if(target[i]) lst = i;
      }

      vi perm;
      FOR(i, 0, fst)   perm.pb(i);
      ROF(i, N, lst+1) perm.pb(i);

      int old = -1;
      if(pos < N){
            //exist special case
            old = fst;
            fst = pos;
            FOR(i, old+1, fst+1) perm.pb(i);
      }

      int last = fst;
      // cout << lst << '\n';
      FOR(i, fst+1, lst+1){
            // cout << dbg(i) << dbg(target[i]) << '\n';
            if(target[i]){
                  // cout << last+1 << ' ' << i-1 << '\n';
                  ROF(j, i, last+1) perm.pb(j);
                  perm.pb(i);
                  last = i;
            }
      }

      if(old != -1) perm.pb(old);
      else perm.pb(fst);

      // cout << sz(perm) << '\n';
      // for(auto it : perm) cout << it << ' '; cout << '\n';
      // assert(sz(perm) == N);
      for(auto it : perm) Remove(it);
}

// g++ -o grader grader.cpp Anna.cpp Bruno.cpp
// if ($?) { g++ -o grader grader.cpp Anna.cpp Bruno.cpp } ; if ($?) { .\grader }

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