oj.uz

Submission #982072

# Submission time Handle Problem Language Result Execution time Memory
982072 2024-05-13T18:52:11 Z steveonalex Robots (IOI13_robots) C++17
100 / 100
 1324 ms 24852 KB 
#include <bits/stdc++.h>
#include "robots.h"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)

// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}

ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }
int putaway(int A,int B,int T,
int X[],int Y[],int W[],int S[]){
    int l = 1, r = T + 1;
    vector<pair<int, int>> stuff(T);
    for(int i = 0; i<T; ++i) stuff[i] = {W[i], S[i]};
    sort(ALL(stuff));
    
    vector<int> weak(A), small(B);
    for(int i = 0; i<A; ++i) weak[i] = X[i];
    for(int i = 0; i<B; ++i) small[i] = Y[i];

    sort(ALL(weak));
    sort(ALL(small));

    reverse(ALL(small));

    while(l < r){
        int mid = (l + r) >> 1;
        priority_queue<int> pq;
        int j = 0;
        for(int i: weak){
            while(j < T && stuff[j].first < i) 
                pq.push(stuff[j++].second);

            for(int j = 0; j < mid; ++j){
                if (pq.empty()) break;
                pq.pop();
            }
        }

        while(j < T){
            pq.push(stuff[j++].second);
        }

        for(int i: small){
            for(int j = 0; j< mid; ++j){
                if (pq.empty()) break;
                if (i > pq.top()){
                    pq.pop();
                }
                else break;
            }
        }

        if (pq.empty()) r = mid;
        else l = mid + 1;
    }

    if (l == T + 1) return -1;
    return l;
}


// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     int a, b, t; cin >> a >> b >> t;
//     int X[a], Y[b], W[t], S[t];
//     for(int i  =0; i<a; ++i) cin >> X[i];
//     for(int i = 0; i<b; ++i) cin >> Y[i];
//     for(int i = 0; i<t; ++i) cin >> W[i];
//     for(int i = 0; i<t; ++i) cin >> S[i];

//     cout << putaway(a, b, t, X, Y, W, S) << "\n";

//     return 0;
// }

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4548 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4544 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 964 ms 23420 KB Output is correct
5 Correct 1264 ms 23384 KB Output is correct
6 Correct 22 ms 6492 KB Output is correct
7 Correct 273 ms 17896 KB Output is correct
8 Correct 631 ms 22596 KB Output is correct
9 Correct 1315 ms 23320 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4544 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 1 ms 4544 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4548 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 9 ms 4700 KB Output is correct
17 Correct 11 ms 4700 KB Output is correct
18 Correct 14 ms 4992 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4544 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4528 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 958 ms 23336 KB Output is correct
11 Correct 1234 ms 23496 KB Output is correct
12 Correct 26 ms 6700 KB Output is correct
13 Correct 235 ms 17912 KB Output is correct
14 Correct 623 ms 22632 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 8 ms 4700 KB Output is correct
22 Correct 1274 ms 23336 KB Output is correct
23 Correct 1279 ms 23540 KB Output is correct
24 Correct 342 ms 24072 KB Output is correct
25 Correct 308 ms 21220 KB Output is correct
26 Correct 407 ms 24852 KB Output is correct
27 Correct 482 ms 22392 KB Output is correct
28 Correct 622 ms 22472 KB Output is correct
29 Correct 1324 ms 24540 KB Output is correct