oj.uz

Submission #971026

# Submission time Handle Problem Language Result Execution time Memory
971026 2024-04-27T20:15:55 Z andro Robots (IOI13_robots) C++14
28 / 100
 155 ms 11220 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].second) {
                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 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 4440 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 2 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 155 ms 9432 KB Output is correct
5 Correct 82 ms 4696 KB Output is correct
6 Correct 22 ms 5336 KB Output is correct
7 Correct 153 ms 11220 KB Output is correct
8 Correct 146 ms 10696 KB Output is correct
9 Correct 145 ms 10944 KB Output is correct

Subtask #3
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 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4644 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Incorrect 1 ms 4440 KB Output isn't correct
13 Halted 0 ms 0 KB -

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 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 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 4440 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4696 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 155 ms 10460 KB Output is correct
11 Correct 92 ms 4696 KB Output is correct
12 Correct 20 ms 5588 KB Output is correct
13 Correct 148 ms 9180 KB Output is correct
14 Correct 146 ms 10436 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 -