제출 #1164290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164290		cjtsai	Fire (BOI24_fire)	C++20	40 / 100	2094 ms	6204 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
 
// Structure to represent an interval on the extended timeline.
struct Interval {
    int start, end;
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    cin >> N >> M;
    
    // We'll build our list of intervals in the extended timeline.
    // Also, we collect candidate starting times (from the original intervals) that lie in [0, M).
    vector<Interval> intervals;
    vector<int> candidateT;
    
    for (int i = 0; i < N; i++){
        int s, e;
        cin >> s >> e;
        candidateT.push_back(s);  // record the original start time
        
        if(s <= e){
            // Non-wrapping interval: add two copies to cover both "halves" of the doubled timeline.
            intervals.push_back({s, e});
            intervals.push_back({s + M, e + M});
        } else {
            // Wrapping interval: transform it into a single interval spanning from s to (e + M)
            intervals.push_back({s, e + M});
        }
    }
    
    // Sort the extended intervals by starting time.
    sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b) {
        return a.start < b.start;
    });
    
    // Remove duplicate candidate starting times.
    sort(candidateT.begin(), candidateT.end());
    candidateT.erase(unique(candidateT.begin(), candidateT.end()), candidateT.end());
    
    int ans = numeric_limits<int>::max();
    
    // For each candidate starting time T (must be in [0, M)),
    // try to cover the interval [T, T + M] using a greedy algorithm.
    for (int T : candidateT) {
        if(T >= M) continue;  // only consider candidate T within the first day
        
        int count = 0;
        int cur = T;
        int target = T + M;
        int j = 0;  // pointer for scanning through intervals
        
        // Greedy covering: extend coverage until we cover [T, T + M]
        while(cur < target) {
            int best = cur;
            // While intervals start at or before our current time, choose the one that extends furthest.
            while(j < intervals.size() && intervals[j].start <= cur) {
                best = max(best, intervals[j].end);
                j++;
            }
            // If we cannot extend our coverage, break out.
            if(best == cur) {
                count = -1;
                break;
            }
            count++;
            cur = best;
        }
        
        if(cur >= target && count != -1) {
            ans = min(ans, count);
        }
    }
    
    // If no candidate provided full coverage, output -1.
    if(ans == numeric_limits<int>::max())
        cout << -1 << "\n";
    else
        cout << ans << "\n";
        
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 0 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26