Submission #935719

#	Time	Username	Problem	Language	Result	Execution time	Memory
935719		thieunguyenhuy	Ancient Machine (JOI21_ancient_machine)	C++17	0 / 100	203 ms	56504 KiB

Anna

#include <bits/stdc++.h>
using namespace std;

#ifndef hwe
    #include "Anna.h"
#endif // hwe

namespace {
    const int LIM = 92;
    long long fib[LIM];
}

void Send(int a);

void mySend(long long num) {
    vector<int> s;
    while (num > 0) s.emplace_back(num & 1), num >>= 1;
    while (s.size() < 64) s.emplace_back(0);
    for (int i = s.size() - 1; i >= 0; --i) {
        Send(s[i]);
//        cout << s[i];
    }
}

void Anna(int n, vector<char> S) {
    fib[0] = 1, fib[1] = 1;
    for (int i = 2; i < LIM; ++i)
        fib[i] = fib[i - 1] + fib[i - 2];

    int p = 0; vector<int> send(n);
    while (p < n && S[p] != 'X') {
        send[p] = 0; ++p;
    }

    while (p < n) {
        send[p] = 1; ++p;
        while (p < n && S[p] != 'Z') {
            send[p] = 0, ++p;
        }
        while (p + 1 < n && S[p + 1] == 'Z') {
            send[p] = 0, ++p;
        }
    }

    for (int i = 0; i < n; ++i) {
        if (send[i]) {
            send.insert(send.begin() + i + 1, 0);
            break;
        }
    }

    int last = -1;
    for (int i = 0; i <= n; ++i) {
        if (i - last == 90) {
            long long num = 0;
            for (int j = i; j > last; --j)
                if (send[j] == 1) num += fib[j - last];
            mySend(num);
            last = i;
        }
    }

    for (auto &x : send) cerr << x;
    cerr << '\n';

    if (last < n) {
        long long num = 0;
        for (int i = n; i > last; --i)
            if (send[i] == 1) num += fib[i - last];
//        cout << num << '\n';
        mySend(num);
    }
}

Bruno

#include <bits/stdc++.h>
using namespace std;

#ifndef hwe
    #include "Bruno.h"
#endif // hwe

#define MASK(n) (1ll << (n))
#define BIT(n, i) ((n) >> (i) & 1)
#define FLIP(n, i) ((n) ^ (1ll << (i)))

bool maximize(int &x, int y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

namespace {
    const int lim = 95;
    long long fib2[lim];
}

void Remove(int d);

void Bruno(int n, int L, vector<int> A) {
    fib2[0] = 1, fib2[1] = 1;
    for (int i = 2; i < lim; ++i)
        fib2[i] = fib2[i - 1] + fib2[i - 2];

    vector<int> decode;
    for (int start = 0; start + 64 + 63 < A.size(); ++start) {
        long long num = 0; vector<int> tmp;
        for (int i = start; i <= start + 63; ++i)
            num = num * 2 + A[i];
        for (int i = 90; i > 0; --i) {
            if (num >= fib2[i]) tmp.emplace_back(1), num -= fib2[i];
            else tmp.emplace_back(0);
        }
        reverse(tmp.begin(), tmp.end());
        for (auto &x : tmp) decode.emplace_back(x);
    }

    assert(A.size() >= 64);
    long long num = 0; vector<int> tmp;
    for (int i = A.size() - 64; i < A.size(); ++i)
        num = num * 2 + A[i];
    for (int i = 90; i > 0; --i) {
        if (num >= fib2[i]) tmp.emplace_back(1), num -= fib2[i];
        else tmp.emplace_back(0);
    }

//    for (auto &x : tmp) cout << x;
//    cout << '\n';
//    reverse(tmp.begin(), tmp.end());
    reverse(tmp.begin(), tmp.end());
    while (decode.size() + tmp.size() > n + 1) tmp.pop_back();

    for (auto &x : tmp) decode.emplace_back(x);

    for (auto &x : decode)
        cerr << x;
    cerr << '\n';

    for (int i = 0; i < decode.size(); ++i) {
        if (decode[i] == 1) {
            decode.erase(decode.begin() + i + 1);
            break;
        }
    }

    int p = 0;
    while (p < decode.size() && decode[p] == 0) {
        Remove(p), ++p;
    }

    int start = p;
    while (p < decode.size()) {
        int cur = p; ++p;
        while (p < decode.size() && decode[p] == 0) ++p;
        for (int i = min(int(decode.size()), p) - 1; i > cur; --i) {
            Remove(i);
        }
        if (p < decode.size()) Remove(p);
    }
    if (start < decode.size()) Remove(start);
}

Compilation message (stderr)

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:33:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int start = 0; start + 64 + 63 < A.size(); ++start) {
      |                         ~~~~~~~~~~~~~~~~^~~~~~~~~~
Bruno.cpp:47:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = A.size() - 64; i < A.size(); ++i)
      |                                 ~~^~~~~~~~~~
Bruno.cpp:58:39: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |     while (decode.size() + tmp.size() > n + 1) tmp.pop_back();
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
Bruno.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 0; i < decode.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~
Bruno.cpp:74:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     while (p < decode.size() && decode[p] == 0) {
      |            ~~^~~~~~~~~~~~~~~
Bruno.cpp:79:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     while (p < decode.size()) {
      |            ~~^~~~~~~~~~~~~~~
Bruno.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         while (p < decode.size() && decode[p] == 0) ++p;
      |                ~~^~~~~~~~~~~~~~~
Bruno.cpp:85:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         if (p < decode.size()) Remove(p);
      |             ~~^~~~~~~~~~~~~~~
Bruno.cpp:87:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     if (start < decode.size()) Remove(start);
      |         ~~~~~~^~~~~~~~~~~~~~~

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