Submission #1025483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025483		socpite	Robots (IOI13_robots)	C++17	100 / 100	1363 ms	24856 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> toys; 
vector<int> RW, RS;

bool check(int val){
    int ptr = 0;
    priority_queue<int> pq;
    for(auto v: RW){
        while(ptr < toys.size() && toys[ptr].first < v)pq.push(toys[ptr++].second);
        for(int _ = 0; _ < val && !pq.empty(); _++)pq.pop();
    }
    while(ptr < toys.size())pq.push(toys[ptr++].second);
    for(auto v: RS){
        if(!pq.empty() && pq.top() >= v)return false;
        for(int _ = 0; _ < val && !pq.empty(); _++)pq.pop();
    }
    return pq.empty();
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    for(int i = 0; i < A; i++)RW.push_back(X[i]);
    for(int i = 0; i < B; i++)RS.push_back(Y[i]);
    sort(RW.begin(), RW.end());
    sort(RS.rbegin(), RS.rend());

    for(int i = 0; i < T; i++){
        toys.push_back({W[i], S[i]});
        if((RW.empty() || W[i] >= RW.back()) && (RS.empty() || S[i] >= RS[0]))return -1;
    }
    sort(toys.begin(), toys.end());
    int l = 1, r = T;
    while(l < r){
        int mid = (l+r)>>1;
        if(check(mid))r = mid;
        else l = mid + 1;
    }
    return l;
}

Compilation message (stderr)

robots.cpp: In function 'bool check(int)':
robots.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         while(ptr < toys.size() && toys[ptr].first < v)pq.push(toys[ptr++].second);
      |               ~~~~^~~~~~~~~~~~~
robots.cpp:15:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     while(ptr < toys.size())pq.push(toys[ptr++].second);
      |           ~~~~^~~~~~~~~~~~~

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