Submission #598513

#	Time	Username	Problem	Language	Result	Execution time	Memory
598513		Jarif_Rahman	Robots (IOI13_robots)	C++17	39 / 100	3090 ms	8488 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

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

    for(int i = 0; i < n; i++) if(W[i] >= X[A-1] && S[i] >= Y[B-1]) return -1;

    vector<int> bw(n), bs(n);

    for(int i = 0; i < n; i++) bw[i] = i, bs[i] = i;

    sort(bw.begin(), bw.end(), [&](int a, int b){
        return W[a] < W[b];
    });
    sort(bs.begin(), bs.end(), [&](int a, int b){
        return S[a] < S[b];
    });

    function<bool(vector<int>, int)>is_distributable_weak = [&](vector<int> toys, int m){
        if(toys.size() > ll(A)*m) return 0;
        sort(toys.begin(), toys.end(), [&](int a, int b){
            return W[a] < W[b];
        });
        int c = m, ls = A-1;
        while(!toys.empty()){
            int x = toys.back();
            toys.pop_back();
            if(W[x] >= X[ls]) return 0;
            c--;
            if(c == 0) c = m, ls--;
        }
        return 1;
    };
    function<bool(vector<int>, int)>is_distributable_small = [&](vector<int> toys, int m){
        if(toys.size() > ll(B)*m) return 0;
        sort(toys.begin(), toys.end(), [&](int a, int b){
            return S[a] < S[b];
        });
        int c = m, ls = B-1;
        while(!toys.empty()){
            int x = toys.back();
            toys.pop_back();
            if(S[x] >= Y[ls]) return 0;
            c--;
            if(c == 0) c = m, ls--;
        }
        return 1;
    };

    int a = 1, b = n;

    while(a < b){
        int md = (a+b)/2;

        vector<int> cur;
        vector<bool> marked(n, 0);

        for(int i = n-1; i >= 0; i--){
            cur.pb(bs[i]);
            if(is_distributable_weak(cur, md)) marked[bs[i]] = 1;
            else cur.pop_back();
        }

        vector<int> sth;
        for(int i = 0; i < n; i++) if(!marked[i]) sth.pb(i);

        if(is_distributable_small(sth, md)) b = md;
        else a = md+1;
    }

    return a;
}

Compilation message (stderr)

robots.cpp: In lambda function:
robots.cpp:28:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   28 |         if(toys.size() > ll(A)*m) return 0;
      |            ~~~~~~~~~~~~^~~~~~~~~
robots.cpp: In lambda function:
robots.cpp:43:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   43 |         if(toys.size() > ll(B)*m) return 0;
      |            ~~~~~~~~~~~~^~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10