Submission #256484

#	Time	Username	Problem	Language	Result	Execution time	Memory
256484		A02	Robots (IOI13_robots)	C++14	53 / 100	2215 ms	54812 KiB

robots

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

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>, std::greater<pair<int, int> > > toys_weight_first;
    multiset<pair<int, int>, std::greater<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 (put_away != T){

        time_taken++;

        for (int i = 0; i < A; i++){
            pair<int, int> current;
            current.first = weak_robots[i];
            current.second = 0;

            multiset<pair<int, int> >::iterator it = toys_weight_first.upper_bound(current);

            if (it != toys_weight_first.end()){

                int w = it -> first;
                int s = it -> second;

                put_away++;

                toys_weight_first.erase(it);
                toys_size_first.erase(toys_size_first.lower_bound(make_pair(s, w)));

            }

        }

        for (int i = 0; i < B; i++){
            pair<int, int> current;
            current.first = small_robots[i];
            current.second = 0;


            multiset<pair<int, int> >::iterator it = toys_size_first.upper_bound(current);

            if (it != toys_size_first.end()){

                int s = it -> first;
                int w = it -> second;

                put_away++;

                toys_size_first.erase(it);
                toys_weight_first.erase(toys_weight_first.lower_bound(make_pair(w, s)));
            }

        }

    }

    return time_taken;
}

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