Submission #257822

#	Time	Username	Problem	Language	Result	Execution time	Memory
257822		A02	Robots (IOI13_robots)	C++14	76 / 100	2744 ms	65536 KiB

robots

#include "robots.h"
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <iostream>
#include <queue>

using namespace std;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {

    vector<int> weak_robots;
    vector<int> small_robots;

    for (int i = 0; i < A; i++){
        weak_robots.push_back(X[i]);
    }

    for (int i = 0; i < B; i++){
        small_robots.push_back(Y[i]);
    }

    sort(weak_robots.begin(), weak_robots.end());
    sort(small_robots.begin(), small_robots.end());

    for (int i = 0; i < T; i++){
        if (weak_robots.size() >= 1 && small_robots.size() >= 1){
            if (weak_robots[weak_robots.size() - 1] <= W[i] && small_robots[small_robots.size() - 1] <= S[i]){
                return -1;
            }
        }
        if (weak_robots.size() == 0){
            if (small_robots[small_robots.size() - 1] <= S[i]){
                return -1;
            }
        }
        if (small_robots.size() == 0){
            if (weak_robots[weak_robots.size() - 1] <= W[i]){
                return -1;
            }
        }
    }

    int put_away = 0;
    int time_taken = 0;

    multiset<pair<int, int> > toys_weight_first;
    multiset<pair<int, int> > toys_size_first;

    for (int i = 0; i < T; i++){
        pair<int, int> p1;
        pair<int, int> p2;

        p1.first = W[i];
        p1.second = S[i];

        p2.first = S[i];
        p2.second = W[i];

        toys_weight_first.insert(p1);
        toys_size_first.insert(p2);
    }

    while (toys_size_first.size() != 0){

        time_taken++;
        //cout << 'a' << toys_size_first.size() << endl;

        priority_queue<pair<int, int> > toys_q_weight_first;
        priority_queue<pair<int, int> > toys_q_size_first;

        multiset<pair<int, int> >::iterator itw = toys_weight_first.begin();

        vector<pair<int, int> > to_deletes;
        vector<pair<int, int> > to_deletew;

        for (int i = 0; i < A; i++){


            while (itw != toys_weight_first.end() && (itw -> first) < weak_robots[i]){
                toys_q_size_first.push(make_pair(itw -> second, itw -> first));
                itw++;
            }

            if (!toys_q_size_first.empty()){
                pair<int, int> c = toys_q_size_first.top();
                toys_q_size_first.pop();
                to_deletes.push_back(c);
            }

        }
        //cout << 'x' << endl;
        for (int i = 0; i < to_deletes.size(); i++){
            toys_size_first.erase(toys_size_first.lower_bound(make_pair(to_deletes[i].first, to_deletes[i].second)));
            toys_weight_first.erase(toys_weight_first.lower_bound(make_pair(to_deletes[i].second, to_deletes[i].first)));
        }
        //cout << 'y' << endl;

        multiset<pair<int, int> >::iterator its = toys_size_first.begin();
        for (int i = 0; i < B; i++){
            //cout << i << endl;
            while (its != toys_size_first.end() && (its -> first) < small_robots[i]){
                toys_q_weight_first.push(make_pair(its -> second, its -> first));
                its++;
            }

            if (!toys_q_weight_first.empty()){
                pair<int, int> c = toys_q_weight_first.top();
                toys_q_weight_first.pop();
                to_deletew.push_back(c);
            }

        }
        //cout << 'z' << endl;
        for (int i = 0; i < to_deletew.size(); i++){
            //cout << to_deletew[i].first << ' ' << to_deletew[i].second << endl;
            //cout << toys_size_first.size() << ' ' << toys_weight_first.size() << endl;
            toys_weight_first.erase(toys_weight_first.lower_bound(make_pair(to_deletew[i].first, to_deletew[i].second)));
            toys_size_first.erase(toys_size_first.lower_bound(make_pair(to_deletew[i].second, to_deletew[i].first)));
        }
        //cout << 'd' << endl;
        //cout << toys_weight_first.size() << ' ' << toys_size_first.size() << endl;

    }

    return time_taken;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:94:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < to_deletes.size(); i++){
                         ~~^~~~~~~~~~~~~~~~~~~
robots.cpp:116:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < to_deletew.size(); i++){
                         ~~^~~~~~~~~~~~~~~~~~~
robots.cpp:45:9: warning: unused variable 'put_away' [-Wunused-variable]
     int put_away = 0;
         ^~~~~~~~

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