Submission #1164299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164299		cjtsai	Tiles (BOI24_tiles)	C++20	0 / 100	58 ms	3912 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
 
struct Point {
    int x, y;
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, M;
    if(!(cin >> N >> M)){
        return 1; // error reading input
    }
    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);
    }
    
    // If the polygon has no vertical extent, output 0.
    if(Ymax <= Ymin){
        cout << 0 << "\n";
        return 0;
    }
    
    // The polygon covers y-values from Ymin to Ymax.
    // We consider each horizontal strip [r, r+1] for r = Ymin, Ymin+1, ..., Ymax-1.
    int rows = Ymax - Ymin;
    // For each row (corresponding to y = r+0.5), record all x–values where a vertical edge is intersected.
    vector<vector<int>> rowXs(rows);
    for (int i = 0; i < N; i++){
        int j = (i + 1) % N;
        // Process only vertical edges.
        if(poly[i].x == poly[j].x){
            int x = poly[i].x;
            int y1 = poly[i].y, y2 = poly[j].y;
            if(y1 > y2) swap(y1, y2);
            // For each integer row r such that r+0.5 lies in [y1, y2),
            // add x to the corresponding row.
            int start = y1;         // smallest integer r with r+0.5 >= y1
            int end = y2 - 1;         // largest integer r with r+0.5 < y2
            for (int r = start; r <= end; r++){
                if(r >= Ymin && r < Ymax)
                    rowXs[r - Ymin].push_back(x);
            }
        }
    }
 
    // For each row, sort the x–values.
    // They should come in pairs that form intervals inside the polygon.
    vector<vector<pair<int,int>>> intervals(rows);
    for (int i = 0; i < rows; i++){
        vector<int>& xs = rowXs[i];
        sort(xs.begin(), xs.end());
        // In some degenerate cases there might be an odd number of intersections.
        if(xs.size() % 2 != 0 && !xs.empty()){
            xs.pop_back(); // drop the last one to keep pairs
        }
        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});
        }
    }
 
    // For each candidate k from 0 to M, check whether the portion of the polygon 
    // with x < k can be covered with 2×2 tiles.
    // Necessary (and in our setting sufficient) conditions:
    //   (a) For every row, the total length (from the union of intervals clipped at x=k)
    //       must be even.
    //   (b) The overall area (sum over rows) 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);
                // Otherwise, the interval contributes 0.
            }
            if(rowLen % 2 != 0){
                valid = false;
                break;
            }
            totalArea += rowLen;
        }
        if(!valid) continue;
        if(totalArea % 4 != 0) continue;
        best = k; // update best candidate
    }
 
    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