Submission #417316

#TimeUsernameProblemLanguageResultExecution timeMemory
417316maomao90Event Hopping 2 (JOI21_event2)C++17
1 / 100
61 ms968 KiB
#include <bits/stdc++.h> using namespace std; template <class T> inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} #define REP(i, s, e) for (int i = s; i < e; i++) #define RREP(i, s, e) for (int i = s; i >= e; i--) typedef long long ll; typedef long double ld; #define MP make_pair #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; #define MT make_tuple typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define pb emplace_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; #define INF 1000000005 #define LINF 1000000000000000005 #define MOD 1000000007 #define MAXN 200005 int n, k; ii lr[MAXN]; vi ans; int main() { scanf("%d%d", &n, &k); REP (i, 0, n) { scanf("%d%d", &lr[i].FI, &lr[i].SE); } REP (i, 0, 1 << n) { if (__builtin_popcount(i) != k) continue; vector<iii> tmp; REP (j, 0, n) { if (i & (1 << j)) { tmp.pb(lr[j].FI, lr[j].SE, j); } } sort(ALL(tmp)); bool pos = 1; REP (j, 1, tmp.size()) { auto [l, r, id] = tmp[j]; auto [pl, pr, pid] = tmp[j - 1]; if (pr > l) { pos = 0; break; } } if (pos) { vi res; for (auto [l, r, id] : tmp) { res.pb(id + 1); } sort(ALL(res)); assert(res.size() == k); if (ans.empty()) { ans = res; } else { bool toswap = 0; REP (j, 0, res.size()) { if (res[j] < ans[j]) { toswap = 1; } else if (res[j] > ans[j]) { break; } } if (toswap) { ans = res; } } } } if (ans.empty()) { printf("-1\n"); } else { for (int i : ans) { printf("%d\n", i); } } return 0; } /* 4 2 1 4 3 5 4 9 7 10 12 3 1 4 1 8 1 3 1 2 1 4 3 8 3 5 3 9 6 11 6 10 6 12 6 7 6 3 1 7 2 5 2 4 4 8 4 7 8 9 6 4 1 3 1 2 2 4 4 5 5 6 6 7 */

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:8:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
   49 |   REP (j, 1, tmp.size()) {
      |        ~~~~~~~~~~~~~~~~                 
event2.cpp:49:3: note: in expansion of macro 'REP'
   49 |   REP (j, 1, tmp.size()) {
      |   ^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from event2.cpp:1:
event2.cpp:63:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |    assert(res.size() == k);
      |           ~~~~~~~~~~~^~~~
event2.cpp:8:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
   68 |     REP (j, 0, res.size()) {
      |          ~~~~~~~~~~~~~~~~               
event2.cpp:68:5: note: in expansion of macro 'REP'
   68 |     REP (j, 0, res.size()) {
      |     ^~~
event2.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
event2.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf("%d%d", &lr[i].FI, &lr[i].SE);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...