oj.uz

Submission #1064033

# Submission time Handle Problem Language Result Execution time Memory
1064033 2024-08-18T08:34:45 Z Theo830 Teams (IOI15_teams) C++17
34 / 100
 4000 ms 30876 KB 
#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

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]){
      |            ~~~~~~~~~~^~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 428 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 356 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 356 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 356 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 360 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 352 KB Output is correct
22 Correct 0 ms 352 KB Output is correct
23 Correct 0 ms 356 KB Output is correct
24 Correct 1 ms 356 KB Output is correct
25 Correct 0 ms 360 KB Output is correct
26 Correct 0 ms 356 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5064 KB Output is correct
2 Correct 14 ms 4848 KB Output is correct
3 Correct 21 ms 6348 KB Output is correct
4 Correct 17 ms 5204 KB Output is correct
5 Correct 13 ms 4304 KB Output is correct
6 Correct 13 ms 4300 KB Output is correct
7 Correct 11 ms 4304 KB Output is correct
8 Correct 11 ms 4304 KB Output is correct
9 Correct 13 ms 6356 KB Output is correct
10 Correct 9 ms 5856 KB Output is correct
11 Correct 9 ms 6088 KB Output is correct
12 Correct 11 ms 6060 KB Output is correct
13 Correct 15 ms 5416 KB Output is correct
14 Correct 18 ms 6348 KB Output is correct
15 Correct 14 ms 4820 KB Output is correct
16 Correct 16 ms 4820 KB Output is correct
17 Correct 14 ms 5068 KB Output is correct
18 Correct 14 ms 5044 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5488 KB Output is correct
2 Correct 29 ms 5340 KB Output is correct
3 Execution timed out 4070 ms 6848 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 24128 KB Output is correct
2 Correct 119 ms 24068 KB Output is correct
3 Execution timed out 4013 ms 30876 KB Time limit exceeded
4 Halted 0 ms 0 KB -