Submission #725082

#	Time	Username	Problem	Language	Result	Execution time	Memory
725082		piOOE	Ancient Machine (JOI21_ancient_machine)	C++17	Compilation error	0 ms	0 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

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) {
      |          ^~~~~~~

/usr/bin/ld: /tmp/ccRGx7Xu.o: in function `main':
grader_bruno.cpp:(.text.startup+0x24d): undefined reference to `Bruno(int, int, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status