Submission #1064033

#TimeUsernameProblemLanguageResultExecution timeMemory
1064033Theo830Teams (IOI15_teams)C++17
34 / 100
4070 ms30876 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e9+7; ll MOD = 998244353; typedef pair<ll,ll> ii; #define iii pair<ii,ll> #define f(i,a,b) for(ll i = a;i < b;i++) #define pb push_back #define vll vector<ll> #define F first #define S second #define all(x) (x).begin(), (x).end() ///I hope I will get uprating and don't make mistakes ///I will never stop programming ///sqrt(-1) Love C++ ///Please don't hack me ///@TheofanisOrfanou Theo830 ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst) ///Stay Calm ///Look for special cases ///Beware of overflow and array bounds ///Think the problem backwards ///Training #include "teams.h" vector<ii>arr; ll n; void init(int N, int a[], int b[]){ n = N; f(i,0,n){ arr.pb(ii(a[i],b[i])); } sort(all(arr)); } int can(int m, int k[]){ ll sum = 0; f(i,0,m){ sum += k[i]; } if(sum > n){ return 0; } ll mp[n+1] = {0}; set<ll>ex; f(i,0,m){ mp[k[i]]++; ex.insert(k[i]); } ll pos = 0; priority_queue<ll>pq; for(auto x:ex){ while(pos < n && arr[pos].F <= x){ pq.push(-arr[pos].S); pos++; } while(!pq.empty() && -pq.top() < x){ pq.pop(); } if(pq.size() < x * mp[x]){ return 0; } ll num = x * mp[x]; while(num--){ pq.pop(); } } return 1; } /* int main() { int N; cin>>N; int *A = (int*)malloc(sizeof(int)*(unsigned int)N); int *B = (int*)malloc(sizeof(int)*(unsigned int)N); for (int i = 0; i < N; ++i) { cin>>A[i]>>B[i]; } init(N, A, B); int Q; cin>>Q; for (int i = 0; i < Q; ++i) { int M; cin>>M; int *K = (int*)malloc(sizeof(int)*(unsigned int)M); for (int j = 0; j < M; ++j) { cin>>K[j]; } printf("%d\n", can(M, K)); } return 0; } */ /* 4 2 4 1 2 2 3 2 3 2 2 1 3 2 1 1 */

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:59:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   59 |         if(pq.size() < x * mp[x]){
      |            ~~~~~~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...