oj.uz

Submission #935572

# Submission time Handle Problem Language Result Execution time Memory
935572 2024-02-29T09:23:52 Z wii Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 39 ms 8072 KB 
#include <vector>
#include <iostream>
using namespace std;

typedef long long ll;

void Anna(int N, std::vector<char> S);
void Send(int a);

void Anna(int N, std::vector<char> S) {
    int cnt[3] = {0};
    for (char x: S) {
        if (x == 'X') ++cnt[0];
        if (x == 'Y') ++cnt[1];
        if (x == 'Z') ++cnt[2];
    }

    vector<int> a;
    a.assign(N, 0);

    int res = 0;
    for (int i = 0; i < N; ++i)
    if (S[i] == 'X') {
        res = i; break;
    }

    for (int i = 1; i <= 17; ++i)
        Send(res >> i - 1 & 1);

    for (int i = 0; i < N; ++i) if (i > res)
        a[i] = (S[i] == 'Z');

    for (int i = 1; i < N; ++i)
        if (a[i - 1] == 1 && a[i] == 1)
            a[i - 1] = 0;

    vector<ll> fibo(65);
    fibo[0] = 1; fibo[1] = 1;
    for (int i = 2; i <= 64; ++i)
        fibo[i] = fibo[i - 1] + fibo[i - 2];

    for (int i = 0; i < N; i += 64) {
        ll hash_num = 0;
        for (int j = i; j < N && j < i + 64; ++j)
            if (a[j] == 1)
                hash_num += fibo[j - i + 1];

        for (int u = 1; u <= 43; ++u)
            Send(hash_num >> u - 1 & 1);
    }
}

#include <deque>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

void Bruno(int N, int L, std::vector<int> A);
void Remove(int d);

// 11 XYZXZYXYXYZ

void Bruno(int N, int L, std::vector<int> A) {
    int ptr = 0;

    int first_x = 0;
    for (int i = 1; i <= 17; ++i) {
        if (A[ptr] == 1)
            first_x += 1LL << i - 1;
        ++ptr;
    }

    vector<int> pos_z;
    pos_z.push_back(first_x);

    vector<ll> fibo(65);
    fibo[0] = 1; fibo[1] = 1;
    for (int i = 2; i <= 64; ++i)
        fibo[i] = fibo[i - 1] + fibo[i - 2];

    int cur = 0;
    for (int i = ptr; i < A.size(); i += 43) {
        ll hash_num = 0;
        for (int j = 1; j <= 43 && i + j - 1 < A.size(); ++j)
            if (A[i + j - 1] == 1)
                hash_num += 1LL << j - 1;

        for (int u = 64; u >= 1; --u) if (hash_num >= fibo[u]) {
            pos_z.push_back(cur + u - 1);
            hash_num -= fibo[u];
        } cur += 64;
    } sort(pos_z.begin(), pos_z.end());

    for (int i = 1; i < pos_z.size(); ++i) {
        int l = pos_z[i - 1];
        int r = pos_z[i];

        // cout << l << " " << r << "\n";

        for (int u = r - 1; u > l; --u)
            Remove(u);
        Remove(r);
    }

    for (int i = pos_z.back() + 1; i < N; ++i)
        Remove(i);

    for (int i = 0; i <= pos_z[0]; ++i)
        Remove(i);
}

Compilation message

Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:28:23: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   28 |         Send(res >> i - 1 & 1);
      |                     ~~^~~
Anna.cpp:49:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   49 |             Send(hash_num >> u - 1 & 1);
      |                              ~~^~~

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:20:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   20 |             first_x += 1LL << i - 1;
      |                               ~~^~~
Bruno.cpp:33:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = ptr; i < A.size(); i += 43) {
      |                       ~~^~~~~~~~~~
Bruno.cpp:35:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int j = 1; j <= 43 && i + j - 1 < A.size(); ++j)
      |                                    ~~~~~~~~~~^~~~~~~~~~
Bruno.cpp:37:38: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   37 |                 hash_num += 1LL << j - 1;
      |                                    ~~^~~
Bruno.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 1; i < pos_z.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~

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 780 KB Output is correct
3 Correct 0 ms 792 KB Output is correct
4 Correct 1 ms 780 KB Output is correct
5 Correct 0 ms 780 KB Output is correct
6 Correct 0 ms 776 KB Output is correct
7 Correct 0 ms 780 KB Output is correct
8 Correct 1 ms 792 KB Output is correct
9 Correct 0 ms 776 KB Output is correct
10 Correct 0 ms 792 KB Output is correct
11 Correct 1 ms 792 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 8072 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -