제출 #398650

#제출 시각아이디문제언어결과실행 시간메모리
3986504fectaEvent Hopping 2 (JOI21_event2)C++17
0 / 100
4 ms1824 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int ll #define ld long double #define pii pair<int, int> #define f first #define s second #define boost() cin.tie(0), cin.sync_with_stdio(0) bool cmp(pii p, pii q) { return p.s < q.s; } const int MN = 3005; int n, k, vis[MN], dp1[MN], dp2[MN]; pii a[MN]; vector<int> xs, ls[MN], rs[MN]; map<int, int> mp; int32_t main() { boost(); cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i].f >> a[i].s; xs.push_back(a[i].f); xs.push_back(a[i].s); } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); for (int i = 0; i < xs.size(); i++) mp[xs[i]] = i + 1; for (int i = 1; i <= n; i++) a[i].f = mp[a[i].f], a[i].s = mp[a[i].s]; vector<int> out; for (int c = 1; c <= k; c++) { vector<pii > v; for (int i = 1; i <= n; i++) { if (vis[i]) continue; ls[a[i].s].push_back(a[i].f); rs[a[i].f].push_back(a[i].s); } memset(dp1, 0, sizeof(dp1)); memset(dp2, 0, sizeof(dp2)); for (int i = 1; i <= xs.size(); i++) { dp1[i] = dp1[i - 1]; for (int p : ls[i]) dp1[i] = max(dp1[i], dp1[p] + 1); } for (int i = xs.size(); i > 0; i--) { dp2[i] = dp2[i + 1]; for (int p : rs[i]) dp2[i] = max(dp2[i], dp2[p] + 1); } for (int i = 1; i <= n; i++) { if (vis[i]) continue; if (dp1[a[i].f] + dp2[a[i].s] >= k - c) { vis[i] = 1; for (int j = 1; j <= n; j++) { if (a[j].f >= a[i].s || a[j].s <= a[i].f) continue; vis[j] = 1; } out.push_back(i); break; } } if (out.size() < c) return 0 * printf("-1\n"); } for (int p : out) printf("%lld\n", p); return 0; }

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

event2.cpp: In function 'int32_t main()':
event2.cpp:34:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < xs.size(); i++) mp[xs[i]] = i + 1;
      |                     ~~^~~~~~~~~~~
event2.cpp:46:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int i = 1; i <= xs.size(); i++) {
      |                         ~~^~~~~~~~~~~~
event2.cpp:66:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   66 |         if (out.size() < c) return 0 * printf("-1\n");
      |             ~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...