Submission #464027

#	Time	Username	Problem	Language	Result	Execution time	Memory
464027		dxz05	Robots (IOI13_robots)	C++14	76 / 100	3073 ms	19844 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 3e2;

#define MP make_pair

int A, B, N, X[MAXN], Y[MAXN], W[MAXN], S[MAXN];
bool removed[MAXN];

bool check(int val){
   // cout << val << endl;
    fill(removed, removed + N, false);

    for (int i = 0; i < A; i++){
        vector<pair<int, int>> vec;
        for (int j = 0; j < N; j++){
            if (removed[j]) continue;
            if (W[j] < X[i]) vec.emplace_back(S[j], j);
        }

        sort(vec.rbegin(), vec.rend());

       // cout << "weak #" << i + 1 << ": ";
        for (int j = 0; j < vec.size(); j++){
            if (j >= val) break;
            int ind = vec[j].second;
            removed[ind] = true;
        //    cout << ind + 1 << ' ';
        }
     //   cout << endl;

    }

    for (int i = B - 1; i >= 0; i--){
        vector<pair<int, int>> vec;
        for (int j = 0; j < N; j++){
            if (removed[j]) continue;
            if (S[j] < Y[i]) vec.emplace_back(S[j], j);
        }

        sort(vec.rbegin(), vec.rend());

        //cout << "small #" << i + 1 << ": ";
        for (int j = 0; j < vec.size(); j++){
            if (j >= val) break;
            int ind = vec[j].second;
            removed[ind] = true;
            //cout << ind + 1 << ' ';
        }
       // cout << endl;
    }

    for (int i = 0; i < N; i++){
        if (!removed[i]) return false;
    }

    return true;
}

int putaway(int _A, int _B, int _N, int _X[], int _Y[], int _W[], int _S[]) {
    A = _A, B = _B, N = _N;
    for (int i = 0; i < A; i++) X[i] = _X[i];
    for (int i = 0; i < B; i++) Y[i] = _Y[i];
    for (int i = 0; i < N; i++) W[i] = _W[i], S[i] = _S[i];

    sort(X, X + A);
    sort(Y, Y + B);

    int l = 1, r = N;

    int ans = -1;
    while (l <= r){
        int mid = (l + r) >> 1;
        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:27: 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 = 0; j < vec.size(); j++){
      |                         ~~^~~~~~~~~~~~
robots.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int j = 0; j < vec.size(); j++){
      |                         ~~^~~~~~~~~~~~

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