Submission #1309118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309118		duongquanghai08	Ancient Machine (JOI21_ancient_machine)	C++20	0 / 100	33 ms	6368 KiB

Anna

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

void Anna(int n, vector<char> S) {
    // Khởi tạo Fibonacci
    vector<long long> f(70, 0);
    f[0] = 1; f[1] = 2;
    for(int i = 2; i <= 63; i++) f[i] = f[i - 1] + f[i - 2];

    vector<int> a(n + 5, 0);
    bool check = false;

    // Bước 1: Đánh dấu các vị trí quan trọng
    // X đầu tiên -> 1
    // Các Z -> 1
    // Còn lại -> 0
    for(int i = 0; i < n; i++) {
        char x = S[i];
        if(x == 'X' && !check) {
            check = true;
            a[i] = 1;
            continue;
        }
        if(!check) a[i] = 0;
        else {
            if(x == 'Z') a[i] = 1;
            else a[i] = 0;
        }
    }

    // Bước 2: Xử lý xung đột (Zeckendorf condition: không có 2 bit 1 liền kề)
    // SỬA: Gán a[i] = 0 thay vì a[i-1] = 0 để tối ưu số lượng bit 1 giữ lại.
    // Logic này tự động bảo vệ X đầu tiên (vì nếu X Z -> 1 1 -> 1 0, X được giữ)
    for(int i = 1; i < n; i++) {
        if(a[i] && a[i - 1]) a[i] = 0;
    }

    // Bước 3: Nén và gửi dữ liệu
    for(int i = 0; i < n; i += 63) {
        long long sum = 0;
        for(int len = 0; i + len < n && len <= 62; len++) {
            if(a[i + len]) sum += f[len];
        }
        for(int j = 0; j <= 43; j++) {
            if((sum >> j) & 1) Send(1);
            else Send(0);
        }
    }
}

Bruno

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

void Bruno(int n, int L, vector<int> A) {
    // Khởi tạo Fibonacci giống hệt Anna
    vector<long long> f(70, 0);
    f[0] = 1; f[1] = 2;
    for(int i = 2; i <= 63; i++) f[i] = f[i - 1] + f[i - 2];

    vector<int> a(n + 100, 0);
    int pre = 0;

    // Giải nén dữ liệu
    for(int i = 0; i < n; i += 63) {
        long long sum = 0;
        for(int j = pre; j <= pre + 43; j++) {
            if(A[j]) sum |= (1LL << (j - pre)); // Dùng 1LL để tránh tràn số
        }
        pre += 44;
        
        // Greedy decoding (Zeckendorf nghịch đảo)
        for(int len = 62; len >= 0; len--) {
            if(sum >= f[len]) {
                a[i + len] = 1;
                sum -= f[len];
            }
        }
    }

    bool check = false;
    int pos = -1;
    stack<int> st;

    // Thực hiện Remove
    for(int i = 0; i < n; i++) {
        // Tìm X đầu tiên (bit 1 đầu tiên xuất hiện)
        if(a[i] == 1 && !check) {
            check = true;
            pos = i;
            continue; // Không remove X ngay, chỉ đánh dấu
        }
        
        // Xóa các phần tử rác trước X đầu tiên
        if(!check) {
            Remove(i);
            continue;
        }

        // Nếu gặp Z (được đánh dấu là 1)
        if(a[i] == 1) {
            // Xả stack (các Y và X thừa ở giữa)
            while(!st.empty()) {
                Remove(st.top());
                st.pop();
            }
            // Remove chính Z này
            Remove(i);
        }
        else {
            // Gặp Y (hoặc X thừa, hoặc Z bị ẩn do nén), đẩy vào stack chờ
            st.push(i);
        }
    }

    // Dọn dẹp stack còn sót lại
    while(!st.empty()) {
        Remove(st.top());
        st.pop();
    }
    
    // Remove X đầu tiên cuối cùng (mỏ neo bên trái)
    if(pos != -1) Remove(pos);
}

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