oj.uz

Submission #935737

# Submission time Handle Problem Language Result Execution time Memory
935737 2024-02-29T13:01:07 Z thieunguyenhuy Ancient Machine (JOI21_ancient_machine) C++17
97 / 100
 285 ms 9892 KB 
#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);
    }
}
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 796 KB Output is correct
2 Correct 0 ms 784 KB Output is correct
3 Correct 0 ms 796 KB Output is correct
4 Correct 0 ms 784 KB Output is correct
5 Correct 0 ms 796 KB Output is correct
6 Correct 1 ms 796 KB Output is correct
7 Correct 0 ms 784 KB Output is correct
8 Correct 1 ms 796 KB Output is correct
9 Correct 0 ms 876 KB Output is correct
10 Correct 0 ms 796 KB Output is correct
11 Correct 0 ms 796 KB Output is correct

Subtask #2
92.0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 256 ms 8784 KB Partially correct
2 Partially correct 274 ms 8832 KB Partially correct
3 Partially correct 258 ms 8864 KB Partially correct
4 Partially correct 261 ms 8848 KB Partially correct
5 Partially correct 280 ms 8888 KB Partially correct
6 Partially correct 256 ms 9040 KB Partially correct
7 Partially correct 259 ms 9040 KB Partially correct
8 Partially correct 259 ms 8784 KB Partially correct
9 Partially correct 258 ms 9128 KB Partially correct
10 Partially correct 261 ms 8788 KB Partially correct
11 Partially correct 278 ms 8792 KB Partially correct
12 Partially correct 258 ms 8796 KB Partially correct
13 Partially correct 261 ms 8764 KB Partially correct
14 Partially correct 266 ms 8812 KB Partially correct
15 Partially correct 258 ms 8852 KB Partially correct
16 Partially correct 255 ms 8788 KB Partially correct
17 Partially correct 268 ms 9320 KB Partially correct
18 Partially correct 265 ms 8544 KB Partially correct
19 Partially correct 271 ms 8992 KB Partially correct
20 Partially correct 255 ms 8784 KB Partially correct
21 Partially correct 258 ms 9148 KB Partially correct
22 Partially correct 259 ms 8840 KB Partially correct
23 Partially correct 256 ms 8824 KB Partially correct
24 Partially correct 254 ms 8852 KB Partially correct
25 Partially correct 269 ms 8540 KB Partially correct
26 Partially correct 285 ms 8840 KB Partially correct
27 Partially correct 269 ms 9892 KB Partially correct
28 Partially correct 267 ms 8800 KB Partially correct
29 Partially correct 259 ms 9288 KB Partially correct
30 Partially correct 261 ms 8788 KB Partially correct
31 Partially correct 283 ms 8564 KB Partially correct
32 Partially correct 256 ms 9008 KB Partially correct
33 Partially correct 254 ms 9008 KB Partially correct