Submission #1164298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164298		cjtsai	Tiles (BOI24_tiles)	C++20	0 / 100	55 ms	3984 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
struct Point {
    int x, y;
};
 
// Main idea:
//   For a candidate k, a valid covering exists if and only if
//   (i) for every horizontal strip (between integer y’s) the total length
//       of the intersection of the polygon with (-∞, k) is even, and
//   (ii) the total area (sum over strips) is divisible by 4.
// 
// Since the polygon is axis–aligned with integer vertices, if we take horizontal
// lines at y = r + 0.5 (for integer r between min and max y–values),
// then (because no such line hits a vertex) the intersections come only from vertical edges.
// We precompute for each row the list of x–coordinates where these intersections occur.
// They come in pairs and form intervals. Then for each candidate k we “clip” each interval
// by intersecting it with (-∞, k) and sum the lengths. (Remember that if an interval straddles k,
// we only count the part to the left.)
// Finally, we require that each row’s length is even and the overall area is a multiple of 4.
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, M;
    cin >> N >> M;
    vector<Point> poly(N);
    int Ymin = INT_MAX, Ymax = 0;
    for (int i = 0; i < N; i++){
        cin >> poly[i].x >> poly[i].y;
        Ymin = min(Ymin, poly[i].y);
        Ymax = max(Ymax, poly[i].y);
    }
    // The polygon covers the vertical range [Ymin, Ymax].
    // We will consider each “row” r corresponding to the horizontal strip [r, r+1]
    // for r = Ymin, Ymin+1, …, Ymax-1.
    int rows = Ymax - Ymin;
    // For each row r, we will compute the x–coordinates where the horizontal line at y = r+0.5
    // crosses the polygon. (Since vertices are integers, y = r+0.5 is “generic” and does not hit a vertex.)
    vector<vector<int>> rowXs(rows); // rowXs[i] corresponds to y = (Ymin+i) + 0.5.
 
    // Process each edge of the polygon.
    // Only vertical edges contribute to intersections with a horizontal line.
    for (int i = 0; i < N; i++){
        int j = (i+1) % N;
        if(poly[i].x == poly[j].x){ // vertical edge
            int x = poly[i].x;
            int y1 = poly[i].y, y2 = poly[j].y;
            if(y1 > y2) swap(y1, y2);
            // This vertical edge runs from y1 to y2.
            // For each integer row r such that y_mid = r + 0.5 lies in [y1, y2),
            // we add x to the list for that row.
            int start = y1;         // r such that r+0.5 >= y1 => r >= y1 - 0.5, so r >= y1.
            int end = y2 - 1;         // r such that r+0.5 < y2 => r <= y2 - 1.
            for (int r = start; r <= end; r++){
                if(r >= Ymin && r < Ymax)
                    rowXs[r - Ymin].push_back(x);
            }
        }
    }
 
    // For each row, sort the x–coordinates and form intervals.
    // Because the polygon is simple the intersections come in pairs.
    vector<vector<pair<int,int>>> intervals(rows);
    for (int i = 0; i < rows; i++){
        vector<int>& xs = rowXs[i];
        sort(xs.begin(), xs.end());
        for (size_t j = 0; j+1 < xs.size(); j += 2){
            int L = xs[j], R = xs[j+1];
            intervals[i].push_back({L, R});
        }
    }
 
    // Now, for each candidate k (0 <= k <= M) we check:
    //  - For each horizontal strip (row), compute the total length of the intervals
    //    (from the precomputed list) intersected with (-∞, k).
    //  - That is, for each interval [L,R], if R <= k add (R-L); if L < k < R add (k - L);
    //    otherwise add 0.
    //  - Each row’s total must be even, and the sum over rows (area) must be divisible by 4.
    int best = 0;
    for (int k = 0; k <= M; k++){
        bool valid = true;
        long long totalArea = 0;
        for (int r = 0; r < rows; r++){
            int rowLen = 0;
            for (auto &pr : intervals[r]){
                int L = pr.first, R = pr.second;
                if(R <= k)
                    rowLen += (R - L);
                else if(L < k)
                    rowLen += (k - L);
                // If L >= k, then that interval contributes 0.
            }
            if(rowLen % 2 != 0){
                valid = false;
                break;
            }
            totalArea += rowLen;
        }
        if(!valid) continue;
        if(totalArea % 4 != 0) continue;
        best = k; // k is valid
    }
 
    cout << best << "\n";
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 9
• Subtask 3: 0 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 22
• Subtask 6: 0 / 25
• Subtask 7: 0 / 10