답안 #905011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
905011 2024-01-12T12:52:38 Z akliu Job Scheduling (CEOI12_jobs) C++11
컴파일 오류
0 ms 0 KB
#include <bits/stdc++.h>
 
using namespace std;
 
void fastio() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}
 
void open(string filename) {
    fastio();
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}
 
typedef long long ll;
#define vll vector<ll>
#define vint vector<int>
#define vbool vector<bool>
#define vpii vector<pii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define ins(x) insert(x)
#define sz() size()
#define lb() lower_bound()
#define ub() upper_bound()
#define rsz resize
#define se second
#define fi first
#define cont continue
 
struct g {
    int day, n;
    bool operator<(const g &y) {
        if (day != y.day) return day < y.day;
        return n < y.n;
    }
};

int N, D, M;
vector<g> v;
multiset<int> machines;
multiset<int> q;

bool check(int m) {
    
    if (m == 2) {
        int ans = 0;
    }
    
    // Iterate to check if the minimum is valid
    machines.clear();
    q.clear();
    int d = 0;
    auto it = v.begin();
    g val = *it;
    while (d != N + 1) {
        if (q.sz()) {
            if (d - *(q.begin()) > D) {
                return false;
            }
        }
        machines.clear();
        val = *it;
        while (machines.sz() != m && q.sz()) {
            machines.ins(*(q.begin()));
            q.erase(q.begin());
        }
        while (val.day == d) {
            if (machines.sz() != m) machines.ins(val.day);
            else q.ins(val.day);
            ++it;
            if (it == v.end()) break;
            val = *it;
        }
        ++d;
    }
    return true;
}

void solve() {
    // Input
    cin >> N >> D >> M;
    for (int i = 0; i < M; ++i) {
        int a; cin >> a;
        v.pb({a, i + 1});
    }
    sort(v.begin(), v.end());

    // Binary search
    int l = 1, r = 1e6, m;
    while (l < r) {
        m = (l + r) / 2;
        if (check(m)) r = m;
        else l = m + 1;
    }
    cout << l << "\n";

    // Iterate once more with the correct minimum
    vector<vint> ans(N + 1);
    machines.clear();
    q.clear();
    int d = 0;
    auto it = v.begin();
    g val = *it;
    while (d != N + 1) {
        machines.clear();
        val = *it;
        while (machines.sz() != l && q.sz()) {
            pii valQ = *(q.begin());
            machines.ins(mp(valQ.fi, valQ.se));
            q.erase(q.begin());
        }
        while (val.day == d) {
            val = *it;
            if (machines.sz() != l) {
                machines.ins(mp(val.day, val.n));
            }
            else q.ins(mp(val.day, val.n));
            ++it;
            if (it == v.end()) break;
        }
        for (auto &x : machines) {
            ans[d].pb(x.se);
        }
        ++d;
    }

    // Output
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j < ans[i].sz(); ++j) {
            cout << ans[i][j] << " ";
        }
        cout << "0\n";
    }
}
 
int main() {
    fastio();
    int tc = 1;
    // cin >> tc;
    while (tc--) {
        solve();
    }
 
    return 0;
}

Compilation message

jobs.cpp: In function 'bool check(int)':
jobs.cpp:50:13: warning: unused variable 'ans' [-Wunused-variable]
   50 |         int ans = 0;
      |             ^~~
jobs.cpp:67:30: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |         while (machines.sz() != m && q.sz()) {
      |                ~~~~~~~~~~~~~~^~~~
jobs.cpp:72:31: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |             if (machines.sz() != m) machines.ins(val.day);
      |                 ~~~~~~~~~~~~~~^~~~
jobs.cpp: In function 'void solve()':
jobs.cpp:111:30: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |         while (machines.sz() != l && q.sz()) {
      |                ~~~~~~~~~~~~~~^~~~
jobs.cpp:112:24: error: conversion from 'const int' to non-scalar type 'std::pair<int, int>' requested
  112 |             pii valQ = *(q.begin());
      |                        ^~~~~~~~~~~~
jobs.cpp:25:24: error: no matching function for call to 'std::multiset<int>::insert(std::pair<int, int>)'
   25 | #define ins(x) insert(x)
      |                        ^
jobs.cpp:113:22: note: in expansion of macro 'ins'
  113 |             machines.ins(mp(valQ.fi, valQ.se));
      |                      ^~~
In file included from /usr/include/c++/10/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from jobs.cpp:1:
/usr/include/c++/10/bits/stl_multiset.h:502:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = int]'
  502 |       insert(const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:502:32: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'const value_type&' {aka 'const int&'}
  502 |       insert(const value_type& __x)
      |              ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_multiset.h:507:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::value_type&&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = int]'
  507 |       insert(value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:507:27: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::multiset<int>::value_type&&' {aka 'int&&'}
  507 |       insert(value_type&& __x)
      |              ~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_multiset.h:532:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::const_iterator, const value_type&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = int]'
  532 |       insert(const_iterator __position, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:532:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_multiset.h:537:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::const_iterator, std::multiset<_Key, _Compare, _Alloc>::value_type&&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = int]'
  537 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:537:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_multiset.h:551:2: note: candidate: 'template<class _InputIterator> void std::multiset<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>]'
  551 |  insert(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:551:2: note:   template argument deduction/substitution failed:
jobs.cpp:25:24: note:   candidate expects 2 arguments, 1 provided
   25 | #define ins(x) insert(x)
      |                        ^
jobs.cpp:113:22: note: in expansion of macro 'ins'
  113 |             machines.ins(mp(valQ.fi, valQ.se));
      |                      ^~~
In file included from /usr/include/c++/10/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from jobs.cpp:1:
/usr/include/c++/10/bits/stl_multiset.h:563:7: note: candidate: 'void std::multiset<_Key, _Compare, _Alloc>::insert(std::initializer_list<_Tp>) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>]'
  563 |       insert(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:563:43: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::initializer_list<int>'
  563 |       insert(initializer_list<value_type> __l)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
jobs.cpp:118:31: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |             if (machines.sz() != l) {
      |                 ~~~~~~~~~~~~~~^~~~
jobs.cpp:25:24: error: no matching function for call to 'std::multiset<int>::insert(std::pair<int, int>)'
   25 | #define ins(x) insert(x)
      |                        ^
jobs.cpp:119:26: note: in expansion of macro 'ins'
  119 |                 machines.ins(mp(val.day, val.n));
      |                          ^~~
In file included from /usr/include/c++/10/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from jobs.cpp:1:
/usr/include/c++/10/bits/stl_multiset.h:502:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = int]'
  502 |       insert(const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:502:32: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'const value_type&' {aka 'const int&'}
  502 |       insert(const value_type& __x)
      |              ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_multiset.h:507:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::value_type&&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = int]'
  507 |       insert(value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:507:27: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::multiset<int>::value_type&&' {aka 'int&&'}
  507 |       insert(value_type&& __x)
      |              ~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_multiset.h:532:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::const_iterator, const value_type&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = int]'
  532 |       insert(const_iterator __position, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:532:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_multiset.h:537:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::const_iterator, std::multiset<_Key, _Compare, _Alloc>::value_type&&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = int]'
  537 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:537:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_multiset.h:551:2: note: candidate: 'template<class _InputIterator> void std::multiset<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>]'
  551 |  insert(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:551:2: note:   template argument deduction/substitution failed:
jobs.cpp:25:24: note:   candidate expects 2 arguments, 1 provided
   25 | #define ins(x) insert(x)
      |                        ^
jobs.cpp:119:26: note: in expansion of macro 'ins'
  119 |                 machines.ins(mp(val.day, val.n));
      |                          ^~~
In file included from /usr/include/c++/10/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from jobs.cpp:1:
/usr/include/c++/10/bits/stl_multiset.h:563:7: note: candidate: 'void std::multiset<_Key, _Compare, _Alloc>::insert(std::initializer_list<_Tp>) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>]'
  563 |       insert(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:563:43: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::initializer_list<int>'
  563 |       insert(initializer_list<value_type> __l)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
jobs.cpp:25:24: error: no matching function for call to 'std::multiset<int>::insert(std::pair<int, int>)'
   25 | #define ins(x) insert(x)
      |                        ^
jobs.cpp:121:20: note: in expansion of macro 'ins'
  121 |             else q.ins(mp(val.day, val.n));
      |                    ^~~
In file included from /usr/include/c++/10/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from jobs.cpp:1:
/usr/include/c++/10/bits/stl_multiset.h:502:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = int]'
  502 |       insert(const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:502:32: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'const value_type&' {aka 'const int&'}
  502 |       insert(const value_type& __x)
      |              ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_multiset.h:507:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::value_type&&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = int]'
  507 |       insert(value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:507:27: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::multiset<int>::value_type&&' {aka 'int&&'}
  507 |       insert(value_type&& __x)
      |              ~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_multiset.h:532:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::const_iterator, const value_type&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = int]'
  532 |       insert(const_iterator __position, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:532:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_multiset.h:537:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::const_iterator, std::multiset<_Key, _Compare, _Alloc>::value_type&&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = int]'
  537 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:537:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_multiset.h:551:2: note: candidate: 'template<class _InputIterator> void std::multiset<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>]'
  551 |  insert(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:551:2: note:   template argument deduction/substitution failed:
jobs.cpp:25:24: note:   candidate expects 2 arguments, 1 provided
   25 | #define ins(x) insert(x)
      |                        ^
jobs.cpp:121:20: note: in expansion of macro 'ins'
  121 |             else q.ins(mp(val.day, val.n));
      |                    ^~~
In file included from /usr/include/c++/10/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from jobs.cpp:1:
/usr/include/c++/10/bits/stl_multiset.h:563:7: note: candidate: 'void std::multiset<_Key, _Compare, _Alloc>::insert(std::initializer_list<_Tp>) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>]'
  563 |       insert(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:563:43: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::initializer_list<int>'
  563 |       insert(initializer_list<value_type> __l)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
jobs.cpp:30:12: error: request for member 'second' in 'x', which is of non-class type 'const int'
   30 | #define se second
      |            ^~~~~~
jobs.cpp:126:25: note: in expansion of macro 'se'
  126 |             ans[d].pb(x.se);
      |                         ^~
jobs.cpp:133:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for (int j = 0; j < ans[i].sz(); ++j) {
      |                           ^
jobs.cpp: In function 'void open(std::string)':
jobs.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~