oj.uz

Submission #957518

# Submission time Handle Problem Language Result Execution time Memory
957518 2024-04-04T00:18:57 Z vjudge1 Robots (IOI13_robots) C++17
53 / 100
 287 ms 22052 KB 
#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>

const ll N = 200069;
const ll mod = 1e9 + 7;

int tc;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    int i, j;
    sort(X, X+A);
    sort(Y, Y+B);

    vector<pii> berat, ukuran;
    for(i = 0; i < T; i++)
    {
        berat.push_back({W[i], i});
        ukuran.push_back({S[i], i});
    }
    sort(berat.begin(), berat.end());
    sort(ukuran.begin(), ukuran.end());

    int l = 1, r = T, ans = -1;
    vector<bool> udah(T+5);
    while(l <= r)
    {
        int mid = (l+r)/2;
        for(i = 0; i < T; i++) udah[i] = 0;

        int res = 0, res2 = 0, bts = 0;
        for(i = 0, j = 0; i < T and j < A;)
        {
            int val = berat[i].fi, id = berat[i].se;
            if(udah[id])
            {
                ++i;
                continue;
            }
            if(bts == mid)
            {
                ++j;
                bts = 0;
                continue;
            }
            if(X[j] > val)
            {
                ++res;
                ++bts;
                udah[id] = 1;
                ++i;
            }
            else
            {
                ++j;
                bts = 0;
            }
        }
        bts = 0;
        for(i = 0, j = 0; i < T and j < B;)
        {
            int val = ukuran[i].fi, id = ukuran[i].se;
            if(udah[id])
            {
                ++i;
                continue;
            }
            if(bts == mid)
            {
                ++j;
                bts = 0;
                continue;
            }
            if(Y[j] > val)
            {
                ++res;
                ++bts;
                udah[id] = 1;
                ++i;
            }
            else
            {
                ++j;
                bts = 0;
            }
        }
        
        for(i = 0; i < T; i++) udah[i] = 0;
        bts = 0;
        for(i = 0, j = 0; i < T and j < B;)
        {
            int val = ukuran[i].fi, id = ukuran[i].se;
            if(udah[id])
            {
                ++i;
                continue;
            }
            if(bts == mid)
            {
                ++j;
                bts = 0;
                continue;
            }
            if(Y[j] > val)
            {
                ++res2;
                ++bts;
                udah[id] = 1;
                ++i;
            }
            else
            {
                ++j;
                bts = 0;
            }
        }
        bts = 0;
        for(i = 0, j = 0; i < T and j < A;)
        {
            int val = berat[i].fi, id = berat[i].se;
            if(udah[id])
            {
                ++i;
                continue;
            }
            if(bts == mid)
            {
                ++j;
                bts = 0;
                continue;
            }
            if(X[j] > val)
            {
                ++res2;
                ++bts;
                udah[id] = 1;
                ++i;
            }
            else
            {
                ++j;
                bts = 0;
            }
        }


        if(res == T or res2 == T)
        {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }

    return ans;
}

// int main()
// {
//     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//     int i, j;

//     int A, B, T;
//     cin >> A >> B >> T;
//     int X[A], Y[B], W[T], S[T];
//     for(i = 0; i < A; i++) cin >> X[i];
//     for(i = 0; i < B; i++) cin >> Y[i];
//     for(i = 0; i < T; i++) cin >> W[i];
//     for(i = 0; i < T; i++) cin >> S[i];

//     cout << putaway(A, B, T, X, Y, W, S) << '\n';
// }

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 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 4440 KB Output is correct
7 Correct 1 ms 4448 KB Output is correct

Subtask #2
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 4692 KB Output is correct
4 Correct 271 ms 21592 KB Output is correct
5 Correct 255 ms 21092 KB Output is correct
6 Correct 35 ms 6820 KB Output is correct
7 Correct 254 ms 20404 KB Output is correct
8 Correct 261 ms 21780 KB Output is correct
9 Correct 256 ms 20912 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 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 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4540 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4540 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4696 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct

Subtask #4
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 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 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4544 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4440 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 4540 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Incorrect 6 ms 4912 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
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 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 273 ms 21588 KB Output is correct
11 Correct 257 ms 21288 KB Output is correct
12 Correct 30 ms 6852 KB Output is correct
13 Correct 250 ms 19888 KB Output is correct
14 Correct 287 ms 22052 KB Output is correct
15 Correct 1 ms 4696 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Incorrect 6 ms 4956 KB Output isn't correct
22 Halted 0 ms 0 KB -