Submission #725083

#	Time	Username	Problem	Language	Result	Execution time	Memory
725083		piOOE	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	68 ms	8492 KiB

Anna

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

using namespace std;

namespace {
    constexpr int k2 = 79;
    constexpr int fib = 113;
    constexpr int LOG = 17;
    using i128 = __int128;

    i128 fibonacci[fib + 1];

    void initFib() {
        fibonacci[0] = 1;
        fibonacci[1] = 2;
        for (int x = 2; x <= fib; ++x) {
            fibonacci[x] = fibonacci[x - 1] + fibonacci[x - 2];
        }
    }

    i128 toBase2(vector<int> s) {
        i128 x = 0;
        reverse(s.begin(), s.end());
        for (int c : s) {
            x = x * 2 + c;
        }
        return x;
    }

    i128 toFib(vector<int> x) {
        i128 res = 0;
        int n = x.size();
        assert(n == fib);
        for (int i = 0; i < n; ++i) {
            res += x[i] * fibonacci[n - i - 1];
        }
        return res;
    }

    vector<int> toVectorFromBase2(i128 x) {
        vector<int> res(k2);
        for (int i = 0; i < k2; ++i) {
            res[i] += x >> i & i128(1);
        }
        return res;
    }

    vector<int> toVectorFromFib(i128 x) {
        vector<int> a(fib);
        for (int i = 0; i < fib; ++i) {
            if (x >= fibonacci[fib - i - 1]) {
                a[i] = 1;
            }
            x -= a[i] * fibonacci[fib - i - 1];
        }
        assert(x == 0);
        return a;
    }
}

void Anna(int n, std::vector<char> s) {
    initFib();
    int x = find(s.begin(), s.end(), 'X') - s.begin();
    int z = n - (find(s.rbegin(), s.rend(), 'Z') - s.rbegin()) - 1;

    if (x > z) {
        return;
    }

    vector<int> a(n);

    for (int i = x + 1; i < n; ++i) {
        if (s[i] == 'Z' && (i + 1 == n || s[i + 1] != 'Z')) {
            a[i] = 1;
        }
    }

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

    while (a.size() % fib) {
        a.push_back(0);
    }

    for (int i = 0; i < a.size(); i += fib) {
        auto f = toFib(vector(a.begin() + i, a.begin() + i + fib));
        auto res = toVectorFromBase2(f);
        for (int j = 0; j < k2; ++j) {
            Send(res[j]);
        }
    }
}

Bruno

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

using namespace std;

namespace {
    constexpr int k2 = 79;
    constexpr int fib = 113;
    constexpr int LOG = 17;
    using i128 = __int128;

    i128 fibonacci[fib + 1];

    void initFib() {
        fibonacci[0] = 1;
        fibonacci[1] = 2;
        for (int x = 2; x <= fib; ++x) {
            fibonacci[x] = fibonacci[x - 1] + fibonacci[x - 2];
        }
    }

    i128 toBase2(vector<int> s) {
        i128 x = 0;
        reverse(s.begin(), s.end());
        for (int c : s) {
            x = x * 2 + c;
        }
        return x;
    }

    i128 toFib(vector<int> x) {
        i128 res = 0;
        int n = x.size();
        assert(n == fib);
        for (int i = 0; i < n; ++i) {
            res += x[i] * fibonacci[n - i - 1];
        }
        return res;
    }

    vector<int> toVectorFromBase2(i128 x) {
        vector<int> res(k2);
        for (int i = 0; i < k2; ++i) {
            res[i] += x >> i & i128(1);
        }
        return res;
    }

    vector<int> toVectorFromFib(i128 x) {
        vector<int> a(fib);
        for (int i = 0; i < fib; ++i) {
            if (x >= fibonacci[fib - i - 1]) {
                a[i] = 1;
            }
            x -= a[i] * fibonacci[fib - i - 1];
        }
        assert(x == 0);
        return a;
    }
}

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

    int fi = 0;

    for (int i = 0; i < LOG; ++i) {
        if (A[i]) {
            fi |= 1 << i;
        }
    }

    assert((L - LOG) % k2 == 0);

    int n = N + (fib - N % fib) % fib;

    vector<int> a(n);

    for (int i = LOG, j = 0; i < L; i += k2, j += fib) {
        auto f = toBase2(vector(A.begin() + i, A.begin() + i + k2));
        auto res = toVectorFromFib(f);
        for (int k = j; k < j + fib; ++k) {
            a[k] = res[k - j];
        }
    }

    for (int i = 0; i < fi; ++i) {
        Remove(i);
    }

    vector<int> stk{fi};

    for (int i = fi + 1; i < N; ++i) {
        if (a[i]) {
            while (stk.size() > 1) {
                Remove(stk.back());
                stk.pop_back();
            }
            Remove(i);
        } else {
            stk.push_back(i);
        }
    }

    for (int x : stk) {
        Remove(x);
    }
}

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int i = 0; i < a.size(); i += fib) {
      |                     ~~^~~~~~~~~~
Anna.cpp: At global scope:
Anna.cpp:49:17: warning: 'std::vector<int> {anonymous}::toVectorFromFib({anonymous}::i128)' defined but not used [-Wunused-function]
   49 |     vector<int> toVectorFromFib(i128 x) {
      |                 ^~~~~~~~~~~~~~~
Anna.cpp:22:10: warning: '{anonymous}::i128 {anonymous}::toBase2(std::vector<int>)' defined but not used [-Wunused-function]
   22 |     i128 toBase2(vector<int> s) {
      |          ^~~~~~~

Bruno.cpp:41:17: warning: 'std::vector<int> {anonymous}::toVectorFromBase2({anonymous}::i128)' defined but not used [-Wunused-function]
   41 |     vector<int> toVectorFromBase2(i128 x) {
      |                 ^~~~~~~~~~~~~~~~~
Bruno.cpp:31:10: warning: '{anonymous}::i128 {anonymous}::toFib(std::vector<int>)' defined but not used [-Wunused-function]
   31 |     i128 toFib(vector<int> x) {
      |          ^~~~~

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