Submission #588632

#	Time	Username	Problem	Language	Result	Execution time	Memory
588632		ogibogi2004	Robots (IOI13_robots)	C++14	28 / 100	197 ms	13744 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXT=1e6+6;
const int MAXN=5e4+6;
struct toy
{
    int w,s;
    bool operator<(const toy &other)const
    {
        if(w!=other.w)return w<other.w;
        return s>other.s;
    }
};
vector<toy>toys;
vector<int>weak,small;
bool used[MAXT];
int fen[MAXT];
void update(int idx,int val)
{
    idx++;
    if(idx<=0)return;
    for(;idx<MAXN;idx+=idx&(-idx))
    {
        fen[idx]+=val;
    }
}
int query(int idx)
{
    if(idx<0)return 0;
    idx++;
    int ret=0;
    for(;idx>0;idx-=idx&(-idx))
    {
        ret+=fen[idx];
    }
    return ret;
}
bool ok(int moves)
{
    memset(used,0,sizeof(used));
    memset(fen,0,sizeof(fen));
    for(int i=0;i<small.size();i++)update(i,moves);
    for(int i=0;i<toys.size();i++)
    {
        int s=toys[i].s;
        int low1=0,high1=small.size()-1,mid1,best1=-1;
        while(low1<=high1)
        {
            mid1=(low1+high1)/2;
            if(small[mid1]>=s)
            {
                best1=mid1;
                low1=mid1+1;
            }
            else high1=mid1-1;
        }
        int j=best1;
        if(query(j)<=0)
        {
            continue;
        }
        else
        {
            used[i]=1;
            update(j,-1);
        }
    }
    int cnt=moves,j=0;
    for(int i=0;i<toys.size();i++)
    {
        if(used[i])continue;
        if(j>=weak.size())return 0;
        if(cnt==0&&j==weak.size()-1)return 0;
        if(cnt==0)
        {
            cnt=moves;
            j++;
        }
        if(toys[i].w>weak[j])return 0;
        cnt--;
    }
    return 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    for(int i=0;i<T;i++)
    {
        toys.push_back({W[i],S[i]});
    }
    sort(toys.rbegin(),toys.rend());
    for(int i=0;i<A;i++)weak.push_back(X[i]-1);
    for(int i=0;i<B;i++)small.push_back(Y[i]-1);
    sort(weak.rbegin(),weak.rend());
    sort(small.rbegin(),small.rend());
    int low=1,high=T,mid,best=T+1;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(ok(mid))
        {
            best=mid;
            high=mid-1;
        }
        else low=mid+1;
    }
    if(best==T+1)
    {
        return -1;
    }
    return best;
}

Compilation message (stderr)

robots.cpp: In function 'bool ok(int)':
robots.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0;i<small.size();i++)update(i,moves);
      |                 ~^~~~~~~~~~~~~
robots.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i<toys.size();i++)
      |                 ~^~~~~~~~~~~~
robots.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0;i<toys.size();i++)
      |                 ~^~~~~~~~~~~~
robots.cpp:73:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         if(j>=weak.size())return 0;
      |            ~^~~~~~~~~~~~~
robots.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         if(cnt==0&&j==weak.size()-1)return 0;
      |                    ~^~~~~~~~~~~~~~~

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