답안 #730329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
730329	2023-04-25T17:29:14 Z	ktkerem	Roller Coaster Railroad (IOI16_railroad)	C++17	컴파일 오류	0 ms	0 KB

railroad

#include <set>
#include <vector>
#include <cstdio>
#include <cassert>
using namespace std;
 
const int MAX = 200010;
 
int n;
pair<int,int> B[MAX];
bool C[MAX];
 
struct str_cmp {
    bool operator()(const int &a, const int &b) {
        if(B[a].first == B[b].first)
            return B[a].second < B[b].second;
        return B[a].first < B[b].first;
    }
};
 
set<int, str_cmp> S;
 
int dfs_loop(int v) {
    //printf("IN %d\n", v);
    if(B[v].second <= B[v].first) {
        C[v] = true;
        S.erase(S.find(v));
        //printf("OUT %d\n", v);
        return B[v].second;
    }
    while(true) {
        B[n + 3] = make_pair(B[v].second, -1);
        auto p = S.lower_bound(n + 3);
        if(p == S.end()) return 1 << 30;
        //printf("%d %d(%d, %d) %d(%d, %d) %d\n", v, *p, B[*p].first, B[*p].second, n + 3, B[n + 3].first, B[n + 3].second, B[v].second);
        //for(auto &x: S) printf("%d(%d, %d)\n", x, B[x].first, B[x].second);
        int g = dfs_loop(*p);
 
        if(g <= B[v].first) {
            C[v] = true;
            S.erase(S.find(v));
            //printf("OUT %d\n", v);
            return g;
        }
        else if(g == 1 << 30) {
            return g;
        }
    }
}
 
long long plan_roller_coaster(vector<int> s, vector<int> t) {
    n = (int) s.size();
 
    // CLEARING
    for(int i = 0; i < n; i++) C[i] = false;
    S.clear();
 
    int maxi = 0;
    for(int i = 0; i < n; i++) {
        B[i] = make_pair(s[i], t[i]);
        S.insert(i);
        maxi = max(maxi, t[i]);
        maxi = max(maxi, s[i]);
    }
    B[n] = make_pair(maxi + 1, 0);
    B[n + 1] = make_pair(-1, 1);
    S.insert(n);
    S.insert(n + 1);
    B[n + 2] = make_pair(maxi + 2, 0);
    auto p  = S.lower_bound(n + 2);
    assert(p == S.end());
    //for(auto &x: S) printf("%d(%d, %d)\n", x, B[x].first, B[x].second);
 
    dfs_loop(n + 1);
    int c = 0;
    for(int i = 0; i < n; i++) if(!C[i]) c++;
 
    return c;
}

Compilation message

In file included from /usr/include/c++/10/set:60,
                 from railroad.cpp:1:
/usr/include/c++/10/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = str_cmp; _Alloc = std::allocator<int>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<int>*]':
/usr/include/c++/10/bits/stl_tree.h:1935:36:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_lower_bound(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type, std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr, const _Key&) [with _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = str_cmp; _Alloc = std::allocator<int>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, str_cmp, std::allocator<int> >::iterator; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type = std::_Rb_tree_node<int>*; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr = std::_Rb_tree_node_base*]'
/usr/include/c++/10/bits/stl_tree.h:2553:36:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::find(const _Key&) [with _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = str_cmp; _Alloc = std::allocator<int>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, str_cmp, std::allocator<int> >::iterator]'
/usr/include/c++/10/bits/stl_set.h:795:25:   required from 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::find(const key_type&) [with _Key = int; _Compare = str_cmp; _Alloc = std::allocator<int>; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, str_cmp, std::allocator<int> >::const_iterator; std::set<_Key, _Compare, _Alloc>::key_type = int]'
railroad.cpp:27:25:   required from here
/usr/include/c++/10/bits/stl_tree.h:780:8: error: static assertion failed: comparison object must be invocable as const
  780 |        is_invocable_v<const _Compare&, const _Key&, const _Key&>,
      |        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~