제출 #1069304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1069304		Essa2006	Fire (BOI24_fire)	C++14	53 / 100	2076 ms	44924 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
   
 
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> All;
    All.reserve(2 * n);
    bool crc = 1;
    vector<array<int, 2>> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i][0] >> A[i][1];
        
        All.push_back(A[i][0]);
        All.push_back(A[i][1]);
        
        if (A[i][0] > A[i][1] && A[i][1] != 0) {
            crc = 0;
        }
    }
    
    sort(all(All));
    map<int, int> new_;
    int cnt = 0;
    for (int i = 0; i < All.size(); i++) {
        if (!i || All[i] != All[i - 1]) {
            new_[All[i]] = cnt++;
        }
    }
    int sz = cnt;
    
    for (int i = 0; i < n; i++) {
        A[i][0] = new_[A[i][0]], A[i][1] = new_[A[i][1]];
    }
    
    int ans = n + 1;
    for (int k = 0; k < n; k++) {
        int cur = A[k][0];
        if (crc) {
            cur = 0;
        }
        vector<array<int, 2>> B = A;
        
        vector<vector<int>> Events(sz + 1);
        for (int i = 0; i < n; i++) {
            if (A[i][0] >= cur) {
                A[i][0] -= cur;
            }   
            else {
                A[i][0] += sz - cur;
            }
            if (A[i][1] >= cur) {
                A[i][1] -= cur;
            }   
            else {
                A[i][1] += sz - cur;
            }
            
            if (A[i][0] > A[i][1]) {
                A[i][1] = sz;
            }
            
            Events[A[i][0]].push_back(i);
        }
        
        
        vector<int> Prf(sz + 1, n + 1);
        Prf[0] = 0;
        int mx = 0;
        for (int i = 0; i <= sz; i++) {
            for (auto j : Events[i]) {
                mx = max(mx, A[j][1]);
            }
            
            Prf[mx] = min(Prf[mx], Prf[i] + 1);
        }
        
        ans = min(ans, Prf[sz]);
        
        swap(A, B);
        
        if (crc) {
            break;
        }
    }
    if (ans == n + 1) { 
        ans = -1;
    }
    
    cout << ans;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < All.size(); i++) {
      |                     ~~^~~~~~~~~~~~

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