oj.uz

Submission #971024

# Submission time Handle Problem Language Result Execution time Memory
971024 2024-04-27T20:13:42 Z andro Robots (IOI13_robots) C++14
53 / 100
 169 ms 10180 KB 
#include <bits/stdc++.h>

#include "robots.h"

using namespace std;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X, X + A);
    sort(Y, Y + B);
    for(int i = 0; i < T; i++) {
        if(W[i] >= X[A - 1] && S[i] >= Y[B - 1]) {
            return - 1;
        }
    }
    vector<pair<int,int>> omg;
    for(int i = 0; i < T; i++) {
        omg.push_back({W[i], S[i]});
    }
    sort(omg.begin(), omg.end());
    int l = 1, r = 1e6, ans = - 1;
    while(l <= r) {
        int mid = (l + r) / 2;
        int pok = A - 1;
        int R = 0;
        int pok1 = B - 1;
        int ok = 0;
        int R1 = 0;
        for(int i = omg.size() - 1; i >= 0; i--) {
            if(pok < 0 && pok1 < 0) {
                ok = 1;
                break;
            }
            if(pok < 0) {
                if(Y[pok1] <= omg[i].second) {
                    ok = 1;
                    break;
                }
                R1 += 1;
                if(R1 >= mid) {
                    R1 = 0;
                    pok1 -= 1;
                }
                continue;
            }
            if(pok1 < 0) {
                if(X[pok] <= omg[i].first) {
                    ok = 1;
                    break;
                }
                R += 1;
                if(R >= mid) {
                    R = 0;
                    pok -= 1;
                }
                continue;
            }
            if(X[pok] <= omg[i].first) {
                if(Y[pok1] <= omg[i].second) {
                    ok = 1;
                    break;
                }
                R1 += 1;
                if(R1 >= mid) {
                    R1 = 0;
                    pok1 -= 1;
                }
                continue;
            }
            if(Y[pok1] <= omg[i].first) {
                if(X[pok] <= omg[i].first) {
                    ok = 1;
                    break;
                }
                R += 1;
                if(R >= mid) {
                    R = 0;
                    pok -= 1;
                }
                continue;
            }
            //! mogu oba gledam onog kome je r manji
            if(R <= R1) {
                R += 1;
                if(R >= mid) {
                    R = 0;
                    pok -= 1;
                }
            }
            else {
                R1 += 1;
                if(R1 >= mid) {
                    R1 = 0;
                    pok1 -= 1;
                }
            }
        }
        ok ^= 1;
        if(ok) {
            r = mid - 1;
            ans = mid;
        }
        else {
            l = mid + 1;
        }
    }
    return ans;
}
/*
int main() {
    int A = 3;
    int B = 2;
    int T = 10;
    int X[3] = {6, 2, 9};
    int Y[2] = {4, 7};
    int W[10] = {4, 8, 2, 7, 1, 5, 3, 8, 7, 10};
    int S[10] = {6, 5, 3, 9, 8, 1, 3, 7, 6, 5};
    cout << putaway(A, B, T, X, Y, W, S);
    int A = 2;
    int B = 1;
    int T = 3;
    int X[2] = {2, 5};
    int Y[1] = {2};
    int W[3] = {3, 5, 2};
    int S[3] = {1, 3, 2};
    cout << putaway(A, B, T, X, Y, W, S);
}*/

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 2 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

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 4440 KB Output is correct
4 Correct 169 ms 9924 KB Output is correct
5 Correct 93 ms 4716 KB Output is correct
6 Correct 24 ms 5336 KB Output is correct
7 Correct 162 ms 9180 KB Output is correct
8 Correct 157 ms 10176 KB Output is correct
9 Correct 155 ms 8924 KB Output is correct

Subtask #3
25.0 / 25.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 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 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 1 ms 4440 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
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 4440 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 Incorrect 1 ms 4444 KB Output isn't correct
12 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 4696 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 164 ms 9180 KB Output is correct
11 Correct 99 ms 4696 KB Output is correct
12 Correct 22 ms 5332 KB Output is correct
13 Correct 157 ms 10180 KB Output is correct
14 Correct 156 ms 9668 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Incorrect 1 ms 4444 KB Output isn't correct
17 Halted 0 ms 0 KB -