제출 #1175451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175451		Zero_OP	Ancient Machine (JOI21_ancient_machine)	C++20	5 / 100	34 ms	6336 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>;

namespace {
      const int MAX = 100;
      const int T = 90;

      ll fib[MAX];

      void process_fibonacci(){ //
            fib[0] = 1; fib[1] = 2; fib[2] = 3;
            FOR(i, 3, MAX) fib[i] = fib[i-2] + fib[i-1];
      }

      int find_compression_length(){ //[fib[T+2] = 1293530146158671551][T = 90][bits = 61][cost = 67832]
            vl fib(91);
            fib[0] = 1; fib[1] = 2;
            fib[2] = 3;
            FOR(i, 3, 91) fib[i] = fib[i-2] + fib[i-1];

            int N = 1e5;
            for(int T = 2; T <= N; ++T){
                  int nT = (N + T - 1) / T;
                  int bits = 32 - __builtin_clz(fib[T+2]);
                  int cost = nT * bits;

                  if(cost <= 70000){
                        cout << dbg(T) << dbg(bits) << dbg(cost) << '\n';
                        return T;
                  }
            }

            return -1;
      }
}

void Anna(int N, std::vector<char> S) {
      int firstX = -1;
      vb target(N, false);
      int special_case = -1;
      FOR(i, 0, N){
            if(S[i] == 'X'){
                  firstX = i;
                  target[i] = 1;
                  while(i+1 < N && S[i+1] == 'Z') ++i;
                  if(i != firstX) special_case = i;
                  FOR(j, i+1, N){
                        if(S[j] == 'Z') {
                              while(j+1 < N && S[j] == S[j+1]) ++j;
                              target[j] = 1;
                        }
                  }
                  break;
            }
      }

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

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

      process_fibonacci();

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

            FOR(i, 0, 61){
                  Send(sum >> i & 1);
            }
      }

      if(special_case == -1){
            FOR(i, 0, 17) Send(1);
      } else{
            FOR(i, 0, 17) Send(special_case >> i & 1);
      }
}

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

namespace {
      const int MAX = 100;
      const int T = 90;

      ll fib[MAX];

      void process_fibonacci(){ //
            fib[0] = 1; fib[1] = 2; fib[2] = 3;
            FOR(i, 3, MAX) fib[i] = fib[i-2] + fib[i-1];
      }

      int find_compression_length(){ //[fib[T+2] = 1293530146158671551][T = 90][bits = 61][cost = 67832]
            vl fib(91);
            fib[0] = 1; fib[1] = 2;
            fib[2] = 3;
            FOR(i, 3, 91) fib[i] = fib[i-2] + fib[i-1];

            int N = 1e5;
            for(int T = 2; T <= N; ++T){
                  int nT = (N + T - 1) / T;
                  int bits = 32 - __builtin_clz(fib[T+2]);
                  int cost = nT * bits;

                  if(cost <= 70000){
                        cout << dbg(T) << dbg(bits) << dbg(cost) << '\n';
                        return T;
                  }
            }

            return -1;
      }
}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void Bruno(int N, int L, std::vector<int> A) {
      if(sz(A) == 1){
            vi perm(N);
            iota(all(perm), 0);
            shuffle(all(perm), rng);
            for(auto it : perm) Remove(it);
            return;
      }

      // assert(sz(A) % 61 == 0); because of special case
      int nBlocks = sz(A) / 61;

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

      process_fibonacci();

      vb target(N);
      if(special_case < N) target[special_case] = 1;
      //leftmost 1 is the first X
      //the other 1 is the Z

      FOR(i, 0, nBlocks){
            int l = i * 61, r = (i + 1) * 61;
            int u = i * 90, v = (i + 1) * 90;
            ll sum = 0;
            FOR(i, l, r){
                  if(A[i]) {
                        sum += 1LL << (i - l);
                  }
            }

            ROF(i, T+1, 0){
                  if(sum >= fib[i]){
                        sum -= fib[i];
                        target[u + i] = true;
                  }
            }
      }

      vi result;
      int first1 = -1, last1 = -1;
      FOR(i, 0, N){
            if(target[i]){
                  first1 = i;
                  break;
            }
      }

      ROF(i, N, 0){
            if(target[i]){
                  last1 = i;
                  break;
            }
      }

      FOR(i, 0, first1)  result.pb(i);
      ROF(i, N, last1+1) result.pb(i);

      int last = first1;
      FOR(i, first1+1, last1+1){
            if(target[i]){
                  ROF(j, i, last+1){
                        result.pb(j);
                  }

                  result.pb(i);
                  last = i;
            }
      }

      result.pb(first1);
      for(auto it : result) {
            Remove(it);
      }
}

// g++ -o grader grader.cpp Anna.cpp Bruno.cpp

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