Submission #964019

#	Time	Username	Problem	Language	Result	Execution time	Memory
964019		n3rm1n	Robots (IOI13_robots)	C++17	0 / 100	20 ms	24480 KiB

robots

#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 (stderr)

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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10