oj.uz

Submission #964019

# Submission time Handle Problem Language Result Execution time Memory
964019 2024-04-16T07:58:05 Z n3rm1n Robots (IOI13_robots) C++17
0 / 100
 20 ms 24480 KB 
#include<bits/stdc++.h>
#include"robots.h"
using namespace std;
const int MAXN = 1e6 + 10;
int a, b, t, x[MAXN], y[MAXN], s[MAXN], w[MAXN];
int taken[MAXN];
int usedx[MAXN], usedy[MAXN];

bool check(int xt)
{
    vector < pair <int, int> > u;
    for (int i = 0; i < t; ++ i)
    {
        u.push_back(make_pair(s[i], i));
    }
    sort(u.begin(), u.end());

    for (int cntx = 0; cntx <= t; ++ cntx)
    {
        memset(taken, 0, sizeof(taken));
        memset(usedx, 0, sizeof(usedx));
        memset(usedy, 0, sizeof(usedy));
        int not_ok = 0;
        int lastx = a-1, lasty = b - 1;
        int ww, idx;
        vector < pair <int, int > > tow, tos;
        for (int j = u.size() - 1; j >= u.size()-cntx; -- j)
        {
            tow.push_back(make_pair(w[u[j].second], u[j].second));
        }
        sort(tow.begin(), tow.end());
        for (int j = u.size()-cntx-1; j >= 0; -- j)
        {
            tos.push_back(u[j]);
        }
        //
        for (int j = tow.size()-1; j >= 0; -- j)
        {
            ww = tow[j].first;
            idx = tow[j].second;
            if(usedx[lastx] == xt)lastx = -1;
            if(lastx == -1)
            {
                not_ok = 1;
                break;
            }
            if(x[lastx] <= ww)
            {
                not_ok = 1;
                break;
            }
            usedx[lastx] ++;
            taken[idx] ++;
        }
        if(not_ok)continue;
        for (int j = tos.size()-1; j >= 0; -- j)
        {
            ww = tos[j].first;
            idx = tos[j].second;
            if(usedy[lasty] == xt)lasty = -1;
            if(lasty == -1)
            {
                not_ok = 1;
                break;
            }
            if(y[lasty] <= ww)
            {
                not_ok = 1;
                break;
            }
            usedy[lasty] ++;
            taken[idx] ++;
        }
        if(not_ok)continue;
        return true;
    }
    return false;
}



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

    for (int i = 0; i < T; ++ i)
    {
        s[i] = S[i];
        w[i] = W[i];
    }
    for (int i = 0; i < A; ++ i)
        x[i] = X[i];
    for (int i = 0; i < B; ++ i)
        y[i] = Y[i];

    a = A;
    b = B;
    t = T;

    int l = 0, r = t, mid, ans = t;
    while(l <= r)
    { mid = (l + r)/2;
        if(check(mid))
        {
            ans = mid;
            r = mid -1;
        }
        else l = mid + 1;
    }
    return ans;
}

Compilation message

robots.cpp: In function 'bool check(int)':
robots.cpp:27:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for (int j = u.size() - 1; j >= u.size()-cntx; -- j)
      |                                    ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 24480 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 24408 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 24396 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 24280 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 24268 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -