제출 #92896

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

robots

/*
    We can binary search the answer

    At each step, we will greedily try to assign toys to the weak robots, then to the small robots

    Total complexity will be O(T log T)

*/

#include"robots.h"
#include<bits/stdc++.h>
using namespace std;
bool scos[1000002];
struct str
{
    int qt, b;
    int pi;
};
str weak[1000002];
str small[1000002];
bool cmp(str a, str b)
{
    if(a.qt == b.qt)
        return a.b < b.b;
    return a.qt < b.qt;
}
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);
    for(int i = 0; i < T; ++i)
    {
        weak[i] = {W[i], S[i], i};
        small[i] = {S[i], W[i], i};
    }
    sort(weak, weak + T, cmp);
  //  for(int i = 0; i < T; ++i)
   //     cout << weak[i].qt << " " << weak[i].b << " " << weak[i].pi << '\n';
    sort(small, small + T, cmp);
    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] > weak[ptra].qt)
                D.push_back(weak[ptra].pi), ++ptra;
            for(int j = 1; j <= mid && !D.empty(); ++j)
                scos[D.back()] = 1, D.pop_back();
        }
        ptra = T-1;
        D.clear();
        for(int i = B-1; i >= 0; --i)
        {
            while(ptra >= 0)
            {
                while(ptra >= 0 && scos[small[ptra].pi])
                    --ptra;
                if(ptra >= 0 && small[ptra].qt < Y[i])
                    D.push_front(small[ptra].pi), --ptra;
                else
                    break;
            }
            for(int j = 1; j <= mid && !D.empty(); ++j)
                scos[D.back()] = 1, D.pop_back();
        }
      //  cout << mid << " " << ptra << '\n';
        bool gg = 1;
        for(int i = 0; i < T; ++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:29: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