제출 #1175441

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175441		Zero_OP	Ancient Machine (JOI21_ancient_machine)	C++20	0 / 100	12 ms	1220 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);
      FOR(i, 0, N){
            if(S[i] == 'X'){
                  firstX = i;
                  target[i] = 1;
                  while(i+1 < N && S[i] == S[i+1]) ++i;
                  FOR(j, i+1, N){
                        if(S[j] == 'Z') {
                              target[j] = 1;
                              while(j+1 < N && S[j] == S[j+1]) ++j;
                        }
                  }
                  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];
            }

            // cout << sum << '\n';

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

/*
g++ -o grader grader.cpp Anna.cpp Bruno.cpp
#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>;

int count_good_removal(const vc& S, const vi& P){
      int N = sz(S);
//      FOR(i, 0, N) cout << S[i]; cout << '\n';
//      FOR(i, 0, N) cout << P[i] << ' '; cout << '\n';
      assert(sz(P) == N);
      vi l(N), r(N);
      for (int i = 0; i < N; i++) {
            l[i] = i - 1;
            r[i] = i + 1;
      }

      int good_count = 0;
      for (int i = 0; i < N; i++) {
            int d = P[i];
            if (l[d] >= 0 && r[d] < N && S[l[d]] == 'X' && S[d] == 'Y' && S[r[d]] == 'Z')
                  good_count++;
            if (l[d] >= 0) r[l[d]] = r[d];
            if (r[d] < N) l[r[d]] = l[d];
      }
      return good_count;
}

int greedy_approach(const vc& S){
      int N = sz(S), firstX = -1, lastZ = -1;
      FOR(i, 0, N){
            if(S[i] == 'X' && firstX == -1) firstX = i;
            if(S[i] == 'Z') lastZ = i;
      }

      if(min(firstX, lastZ) == -1 || firstX > lastZ){
            return 0;
      }

      vi result;
      FOR(i, 0, firstX)   result.pb(i);
      ROF(i, N, lastZ+1)  result.pb(i);

      int last_removed = firstX;
      FOR(i, firstX+1, lastZ+1){
            if(S[i] == 'Z'){
                  ROF(j, i, last_removed+1){
                        result.pb(j);
                  }

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

      result.pb(firstX);
//      for(auto it : result) cout << it << ' '; cout << '\n'; exit(0);
      assert(sz(result) == N);
      return count_good_removal(S, result);
}

int main(){
      ios_base::sync_with_stdio(0); cin.tie(0);

      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
//      int N;
//      cin >> N;
//      vc S(N);
//      FOR(i, 0, N) {
//            char c; cin >> c;
//            S[i] = c;
//      }
//
//      int greedy_solution = greedy_approach(S);
//      int brute_solution = 0;
//
//      vi perm(N);
//      iota(all(perm), 0);
//      do{
//            maximize(brute_solution, count_good_removal(S, perm));
//      } while(next_permutation(all(perm)));
//
//      cout << greedy_solution << ' ' << brute_solution << '\n';
//
//



      return 0;
}
*/

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

      // FOR(i, 0, L) cout << A[i]; cout << '\n';
      // cout << "wtf\n";

      assert(sz(A) % 61 == 0);
      int nBlocks = sz(A) / 61;

      process_fibonacci();

      vb target(N);
      //leftmost 1 is the first X
      //the other 1 is the Z

      // cout << sz(A) << '\n';
      // cout << dbg(nBlocks) << '\n';
      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]) {
                        // cout << dbg(i - l) << '\n';
                        sum += 1LL << (i - l);
                  }
            }

            // cout << sum << '\n';

            assert(sum < fib[T+2]);
            ROF(i, T+1, 0){
                  if(sum >= fib[i]){
                        // cout << dbg(fib[i]) << '\n';
                        sum -= fib[i];
                        // cout << dbg(u + i) << '\n';
                        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;
            }
      }

      assert(first1 != -1);

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

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

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

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

      result.pb(first1);
      // for(auto it : result) cout << it << ' '; cout << '\n';
//      assert(sz(result) == N);
      for(auto it : result) Remove(it);
}

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

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