제출 #92899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92899		stefdasca	로봇 (IOI13_robots)	C++14	14 / 100	327 ms	11740 KiB

robots

/*
    As it is usual for such problems, we can binary search the answer

    At each step, we will try to assign toys to the weak robots, then to the small robots. Since we will use a priority queue, checking will be done
at each step in O(T log T)

    Therefore, the total complexity will be O(T log^2 T)

*/

#include"robots.h"
#include<bits/stdc++.h>
using namespace std;
bool scos[1000002];
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    int j = 0;
    sort(X, X+A);
    sort(Y, Y+B);
    vector<pair<int, int> >v;
    for(int i = 0; i < T; ++i)
        v.push_back({W[i], S[i]});
    sort(v.begin(), v.end());
    int b = 0;
    int e = 10000002;
    bool findd = 0;
    int ans = 0;
    while(b <= e)
    {
        int mid = (b + e) / 2;
        for(int i = 0; i < T; ++i)
            scos[i] = 0;
        deque<int>D;
        int ptra = 0;
        for(int i = 0; i < A; ++i)
        {
            while(ptra < T && X[i] > v[ptra].first)
                D.push_back(ptra), ++ptra;
            for(int j = 1; j <= mid && !D.empty(); ++j)
                scos[D.back()] = 1, D.pop_back();
        }
        vector<int>v2;
        for(int i = 0; i < T; ++i)
            if(!scos[i])
                v2.push_back(v[i].second);
        sort(v2.begin(), v2.end());
        for(int i = 0; i < v2.size(); ++i)
            scos[i] = 0;
        D.clear();
        ptra = v2.size() - 1;
        for(int i = B-1; i >= 0; --i)
        {
            while(ptra >= 0 && v2[ptra] < Y[i])
                D.push_front(ptra), --ptra;
            for(int j = 1; j <= mid && !D.empty(); ++j)
                scos[D.back()] = 1, D.pop_back();
        }
        bool gg = 1;
        for(int i = 0; i < v2.size(); ++i)
            if(!scos[i])
                gg = 0;
        if(gg)
            findd = 1, ans = mid, e = mid - 1;
        else
            b = mid + 1;
    }
    if(!findd)
        return -1;
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:47:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < v2.size(); ++i)
                        ~~^~~~~~~~~~~
robots.cpp:59:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < v2.size(); ++i)
                        ~~^~~~~~~~~~~
robots.cpp:17:9: warning: unused variable 'j' [-Wunused-variable]
     int j = 0;
         ^

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