제출 #592724

#제출 시각아이디문제언어결과실행 시간메모리
592724l_reho팀들 (IOI15_teams)C++14
34 / 100
4075 ms9024 KiB
#include <bits/stdc++.h> using namespace std; vector<pair<int, int>> ranges; int n; bool compare(pair<int, int> p1, pair<int, int> p2){ return (p1.second < p2.second) || ((p1.second == p2.second && p1.first < p2.first)); } void init(int N, int A[], int B[]) { n = N; for(int i = 0; i < N; i++) ranges.push_back({A[i], B[i]}); sort(ranges.begin(), ranges.end(), compare); } int can(int M, int K[]) { vector<bool> assigned(n, false); sort(K, K+M); for(int i = 0; i < M; i++){ int cnt = 0; bool ok = false; int init = 0; // naive O(N) // posso contare il numero di studenti che vanno bene tramite una binary search // però poi come li marchio assegnati? for(int j = init; j < n; j++){ int start = ranges[j].first; int end = ranges[j].second; if(start <= K[i] && end >= K[i] && !assigned[j]) cnt++, assigned[j] = true; if(cnt == K[i]){ok = true; init=j+1; break;} } // logn O(logN) // contare il numero di intervalli che contengono un'altro intervallo // A = cnt({K[i], K[i+1]}) // B = cnt({K[i+1], K[i+1]}) B - A se A <= K[i], altrimenti tolgo K[i] if(!ok) return 0; } return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...