Submission #935737

#	Time	Username	Problem	Language	Result	Execution time	Memory
935737		thieunguyenhuy	Ancient Machine (JOI21_ancient_machine)	C++17	97 / 100	285 ms	9892 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] == 1) {
            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 += 64) {
        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);
    }

    reverse(tmp.begin(), tmp.end());
    while (!tmp.empty() && decode.size() + tmp.size() > n + 1) tmp.pop_back();

//    for (auto &x : tmp) cerr << x;
//    cerr << '\n';
    for (auto x : tmp) decode.emplace_back(x);

//    for (int i = 0; i < n; ++i)
//        Remove(i);
//    return;

    int sum = 0;
    for (auto &x : decode) {
        sum += x;
    }

    if (sum == 0) decode.pop_back();

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

    for (int i = 0; i < decode.size(); ++i) {
        if (decode[i] == 1) {
//            cout << i << '\n';
            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 += 64) {
      |                         ~~~~~~~~~~~~~~~~^~~~~~~~~~
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:55:55: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     while (!tmp.empty() && decode.size() + tmp.size() > n + 1) tmp.pop_back();
      |                            ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
Bruno.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (int i = 0; i < decode.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~
Bruno.cpp:85:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     while (p < decode.size() && decode[p] == 0) {
      |            ~~^~~~~~~~~~~~~~~
Bruno.cpp:90:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     while (p < decode.size()) {
      |            ~~^~~~~~~~~~~~~~~
Bruno.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         while (p < decode.size() && decode[p] == 0) ++p;
      |                ~~^~~~~~~~~~~~~~~
Bruno.cpp:96:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         if (p < decode.size()) Remove(p);
      |             ~~^~~~~~~~~~~~~~~
Bruno.cpp:98:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     if (start < decode.size()) Remove(start);
      |         ~~~~~~^~~~~~~~~~~~~~~

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