제출 #92889

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

robots

#include"robots.h"
#include<bits/stdc++.h>
using namespace std;
bool scos[1000002];
int pos[1000002];
struct str
{
    int quantity;
    bool tip;
    int pi;
};
str v[2000002];
bool cmp(str a, str b)
{
    if(a.quantity == b.quantity)
        return pos[a.pi] > pos[b.pi];
    return a.quantity < b.quantity;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    int j = 0;
    for(int i = 0; i < T; ++i)
    {
        if(W[i] <= X[A-1])
            ++pos[i];
        if(S[i] <= Y[B-1])
            ++pos[i];
        v[j++] = {W[i], 0, i};
        v[j++] = {S[i], 1, i};

    }
    sort(X, X+A);
    sort(Y, Y+B);
    sort(v, v + j, 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;
        int Pa = A-1;
        int Pb = B-1;
        int Ta = mid;
        int Tb = mid;
      //  if(mid == 3)
       //     cout << mid << '\n';
        for(int i = j-1; i >= 0; --i)
        {
          //  if(mid == 3)
            //    cout << "orz   " << Pa << " " << Ta << " " << Pb << " " << Tb << '\n';
            if(scos[v[i].pi])
                continue;
            if(v[i].tip == 0 && (Pa + Ta == 0))
                continue;
            if(v[i].tip == 1 && (Pb + Tb == 0))
                continue;
            if(v[i].tip == 0 && v[i].quantity <= X[Pa])
            {
               // if(mid == 3)
                //    cout << 1 << " " << v[i].pi << " " << v[i].quantity << " " << X[Pa] << '\n';
                scos[v[i].pi] = 1;
                --Ta;
                if(Ta == 0 && Pa)
                    --Pa, Ta = mid;
            }
            if(v[i].tip == 1 && v[i].quantity <= Y[Pb])
            {
              //  if(mid == 3)
                //    cout << 2 << " " << v[i].pi << " " << v[i].quantity << " " << Y[Pb] << '\n';
                scos[v[i].pi] = 1;
                --Tb;
                if(Tb == 0 && Pb)
                    --Pb, Tb = mid;
            }
        }
        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;
}

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