Submission #221876

#	Time	Username	Problem	Language	Result	Execution time	Memory
221876		laoriu	Robots (IOI13_robots)	C++14	90 / 100	3065 ms	25372 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"

using namespace std;
typedef pair <int,int> pp;
pp A[1000002];
int pos[1000002],nextt[1000002],C[1000002];
int check(int a,int b,int n,int X[],int Y[],int k)
{
    for (int i=0;i<=b;i++)
        nextt[i]=i,C[i]=0;
    vector <int> P;
    for (int i=n-1;i>=0;i--)
    {
        int p=pos[i];
        int x=p;
        while (C[p]==k)
        {
            p=nextt[p+1];
           // cerr<<p<<endl;
        }
        if (p==b) P.push_back(A[i].first);
        else
        {
            assert(C[p]<k);
            C[p]++;
            if (C[p]==k) p=nextt[p+1];
        }
        while (C[x]==k)
        {
            nextt[x]=p;
            x=nextt[x+1];
        }
    }
    //if ((long long) P.size()>(long long)a*k) return 0;
   /* cout<<"cac "<<k<<endl;
    for (int i=0;i<P.size();i++)
        cout<<P[i]<<' ';cout<<endl;*/
    for (int i=0;i<P.size();i+=k)
        if (i/k>=a||P[i]>X[i/k]) return 0;
    return 1;
}
int putaway(int a,int b,int n,int X[],int Y[],int W[],int S[])
{
    sort(X,X+a,greater<int>());sort(Y,Y+b);

    for (int i=0;i<n;i++)
    {
        W[i]++;S[i]++;
        A[i].first=W[i];
        A[i].second=S[i];
    }
    sort(A,A+n);
    for (int i=0;i<n;i++)
    {
        int d=0;int c=b-1;
        pos[i]=b;
        while (d<=c)
        {
            int mid=(d+c)/2;
            if (Y[mid]>=A[i].second) {pos[i]=mid;c=mid-1;}
            else d=mid+1;
        }
       // cout<<A[i].first<<' '<<A[i].second<<' '<<pos[i]<<endl;
    }
    int d=1;int c=n;int res=-1;
    while (d<=c)
    {
        int mid=(d+c)/2;
        if (check(a,b,n,X,Y,mid)) {res=mid;c=mid-1;}
        else d=mid+1;
    }
    return res;
}
/*int main()
{
    freopen("robotz.inp","r",stdin);
    freopen("robotz.out","w",stdout);
    int a,b,n,X[50002],Y[50002],W[1000002],S[1000002];
    cin>>a>>b>>n;
    for (int i=0;i<a;i++) cin>>X[i];
    for (int i=0;i<b;i++) cin>>Y[i];
    for (int i=0;i<n;i++) cin>>W[i]>>S[i];
    cout<<putaway(a,b,n,X,Y,W,S);
}*/

Compilation message (stderr)

robots.cpp: In function 'int check(int, int, int, int*, int*, int)':
robots.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<P.size();i+=k)
                  ~^~~~~~~~~

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