Submission #1337757

#TimeUsernameProblemLanguageResultExecution timeMemory
1337757nguyengiabach1201BOI Acronym (BOI25_boi)C++20
0 / 100
1 ms580 KiB
#include <iostream>
#include <vector>

using namespace std;

/**
 * Bài toán: BOI (Baltic Olympiad in Informatics 2025) [cite: 1, 3]
 * Mục tiêu: Xác định các vị trí của ký tự 'B' dựa trên số lần xuất hiện 
 * của ký tự phổ biến nhất trong mọi xâu con[cite: 14, 17].
 */

int M[2005][2005];

int main() {
    // Tối ưu hóa nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0; // Đọc độ dài n của acronym [cite: 19, 28]

    // Đọc ma trận các gợi ý M[l][r] 
    // Ma trận được cho dưới dạng tam giác:
    // Hàng 1: M[1][1], M[1][2], ..., M[1][n]
    // Hàng 2: M[2][2], M[2][3], ..., M[2][n]
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            cin >> M[i][j];
        }
    }

    vector<int> b_positions;

    /**
     * Thuật toán kiểm tra từng vị trí i: 
     * Một vị trí i là 'B' nếu và chỉ nếu việc thêm nó vào làm tăng 
     * giá trị phổ biến nhất (M) của TẤT CẢ các xâu con kết thúc tại i.
     * Tức là: M[l][i] = M[l][i-1] + 1 với mọi 1 <= l <= i.
     */
    for (int i = 1; i <= n; i++) {
        bool is_B = true;
        for (int l = 1; l <= i; l++) {
            // Với l = i, M[i][i-1] mặc định là 0
            int previous_max = (l < i) ? M[l][i - 1] : 0;
            
            if (M[l][i] != previous_max + 1) {
                is_B = false;
                break;
            }
        }
        
        if (is_B) {
            b_positions.push_back(i);
        }
    }

    // Xuất các vị trí của 'B' theo thứ tự tăng dần [cite: 24, 30]
    for (int i = 0; i < b_positions.size(); i++) {
        cout << b_positions[i] << (i == b_positions.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...