# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
417316 | 2021-06-03T14:46:46 Z | maomao90 | Event Hopping 2 (JOI21_event2) | C++17 | 61 ms | 968 KB |
#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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Incorrect | 26 ms | 968 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 2 ms | 288 KB | Output is correct |
5 | Correct | 2 ms | 204 KB | Output is correct |
6 | Correct | 4 ms | 300 KB | Output is correct |
7 | Correct | 7 ms | 204 KB | Output is correct |
8 | Correct | 5 ms | 300 KB | Output is correct |
9 | Correct | 4 ms | 204 KB | Output is correct |
10 | Correct | 5 ms | 204 KB | Output is correct |
11 | Correct | 61 ms | 276 KB | Output is correct |
12 | Correct | 5 ms | 204 KB | Output is correct |
13 | Correct | 4 ms | 300 KB | Output is correct |
14 | Correct | 5 ms | 204 KB | Output is correct |
15 | Correct | 4 ms | 204 KB | Output is correct |
16 | Correct | 58 ms | 280 KB | Output is correct |
17 | Correct | 39 ms | 204 KB | Output is correct |
18 | Correct | 8 ms | 204 KB | Output is correct |
19 | Correct | 31 ms | 204 KB | Output is correct |
20 | Correct | 59 ms | 204 KB | Output is correct |
21 | Correct | 4 ms | 300 KB | Output is correct |
22 | Correct | 13 ms | 296 KB | Output is correct |
23 | Correct | 50 ms | 204 KB | Output is correct |
24 | Correct | 4 ms | 204 KB | Output is correct |
25 | Correct | 4 ms | 204 KB | Output is correct |
26 | Correct | 5 ms | 332 KB | Output is correct |
27 | Correct | 4 ms | 204 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 2 ms | 288 KB | Output is correct |
5 | Correct | 2 ms | 204 KB | Output is correct |
6 | Correct | 4 ms | 300 KB | Output is correct |
7 | Correct | 7 ms | 204 KB | Output is correct |
8 | Correct | 5 ms | 300 KB | Output is correct |
9 | Correct | 4 ms | 204 KB | Output is correct |
10 | Correct | 5 ms | 204 KB | Output is correct |
11 | Correct | 61 ms | 276 KB | Output is correct |
12 | Correct | 5 ms | 204 KB | Output is correct |
13 | Correct | 4 ms | 300 KB | Output is correct |
14 | Correct | 5 ms | 204 KB | Output is correct |
15 | Correct | 4 ms | 204 KB | Output is correct |
16 | Correct | 58 ms | 280 KB | Output is correct |
17 | Correct | 39 ms | 204 KB | Output is correct |
18 | Correct | 8 ms | 204 KB | Output is correct |
19 | Correct | 31 ms | 204 KB | Output is correct |
20 | Correct | 59 ms | 204 KB | Output is correct |
21 | Correct | 4 ms | 300 KB | Output is correct |
22 | Correct | 13 ms | 296 KB | Output is correct |
23 | Correct | 50 ms | 204 KB | Output is correct |
24 | Correct | 4 ms | 204 KB | Output is correct |
25 | Correct | 4 ms | 204 KB | Output is correct |
26 | Correct | 5 ms | 332 KB | Output is correct |
27 | Correct | 4 ms | 204 KB | Output is correct |
28 | Incorrect | 52 ms | 360 KB | Output isn't correct |
29 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Incorrect | 26 ms | 968 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |