Submission #65367

#	Time	Username	Problem	Language	Result	Execution time	Memory
65367		yp155136	Robots (IOI13_robots)	C++14	100 / 100	2432 ms	13700 KiB

robots

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

const int N = 1000006;

int x[N],y[N],w[N],s[N];
typedef pair<int,int> pii;
#define F first
#define S second

const int INF = 2e9 + 7;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    int n=T,a=A,b=B;
    for (int i=0;A>i;i++) x[i] = X[i];
    if (a) sort(x,x+a);
    for (int i=0;B>i;i++) y[i] = Y[i];
    if (b) sort(y,y+b);
    //cout << "(T, a, b) = " << "( " << T << " , " << a << " , " << b << " ) " <<endl;
    vector<pii> v;
    for (int k=0;T>k;k++)
    {
        if (a>0 && W[k] >= x[a-1] && b==0) return -1;
        if (b>0 && S[k] >= y[b-1] && a==0) return -1;
        if (a && b)
        {
            if (W[k] >= x[a-1] && S[k] >= y[b-1]) return -1;
        }
        v.push_back(make_pair(W[k],S[k]));
        //cout << "k = " << k << " , v = ( " << W[k] << " , " << S[k] << " ) " << endl;
    }
    sort(v.begin(),v.end());
    v.push_back(make_pair(INF,INF));
    int L=0,R=T;
    x[a] = INF + 880301;
    while (R-L != 1)
    {
        int mid=(L+R)>>1;
        priority_queue<int> pq;
        int ptr=0;
        for (int i=0;T>=i;i++)
        {
            while (x[ptr] <= v[i].F)
            {
                ++ptr;
                int cnt=mid;
                while (cnt-- && pq.size()) pq.pop();
            }
            if (i == T) break;
            pq.push(v[i].S);
        }
        bool can = true;
        //cout << "mid = " << mid << " , sz = " << pq.size() << endl;
        for (int i=b-1;i>=0;i--)
        {
            int cnt=mid;
            while (cnt-- && pq.size())
            {
                int x=pq.top();
                pq.pop();
                if (x >= y[i])
                {
                    can = false;
                    break;
                }
            }
            if (!can) break;
        }
        if (pq.size()) can = false;
        if (!can) L = mid;
        else R = mid;
    }
    return R;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:15:9: warning: unused variable 'n' [-Wunused-variable]
     int n=T,a=A,b=B;
         ^

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