제출 #722533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
722533		minhnhatnoe	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	3059 ms	6956 KiB

event2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> l;
struct node{
    int left, right;
    int idx;
};
vector<int> pos;
vector<node> a;
int test(int l, int r){
    int cnt = 0;
    int ptr = 0;
    for (int i=0; i<a.size(); i++){
        if (a[i].idx == -1) continue;
        if (l <= a[i].left && a[i].left < r) continue;
        if (l < a[i].right && a[i].right <= r) continue;
        if (a[i].left < ptr) continue;
        cnt++;
        ptr = a[i].right;
    }
    return cnt;
}
void erase_inter(int l, int r){
    vector<node> nxta;
    for (int i=0; i<a.size(); i++){
        if (l <= a[i].left && a[i].left < r) continue;
        if (l < a[i].right && a[i].right <= r) continue;
        nxta.push_back(a[i]);
    }
    a = move(nxta);
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, k; cin >> n >> k;
    l.resize(n), a.resize(n);
    for (int i=0; i<n; i++){
        cin >> a[i].left >> a[i].right;
        a[i].idx = i;
        l[i] = a[i].left;
    }
    sort(l.begin(), l.end());
    l.resize(unique(l.begin(), l.end()) - l.begin());
    for (int i=0; i<a.size(); i++){
        a[i].left = lower_bound(l.begin(), l.end(), a[i].left) - l.begin();
        a[i].right = lower_bound(l.begin(), l.end(), a[i].right) - l.begin();
    }
    sort(a.begin(), a.end(), [](const node &x, const node &y){
        return x.right < y.right;
    });
    if (test(-1, -1) < k){
        cout << "-1\n";
        return 0;
    }
    while (k){
        pos.assign(n, -1);
        for (int i=0; i<a.size(); i++){
            if (a[i].idx == -1) continue;
            pos[a[i].idx] = i;
        }
        for (int i=0; i<pos.size(); i++){
            if (pos[i] == -1) continue;
            if (test(a[pos[i]].left, a[pos[i]].right) + 1 < k){
                a[pos[i]].idx = -1;
                continue;
            }
            a[pos[i]].idx = -1;
            erase_inter(a[pos[i]].left, a[pos[i]].right);
            cout << i+1 << "\n";
            break;
        }
        k--;
    }
}

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

event2.cpp: In function 'int test(int, int)':
event2.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i=0; i<a.size(); i++){
      |                   ~^~~~~~~~~
event2.cpp: In function 'void erase_inter(int, int)':
event2.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i=0; i<a.size(); i++){
      |                   ~^~~~~~~~~
event2.cpp: In function 'int main()':
event2.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i=0; i<a.size(); i++){
      |                   ~^~~~~~~~~
event2.cpp:57:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int i=0; i<a.size(); i++){
      |                       ~^~~~~~~~~
event2.cpp:61:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int i=0; i<pos.size(); i++){
      |                       ~^~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61