Submission #589483

#	Time	Username	Problem	Language	Result	Execution time	Memory
589483		ogibogi2004	Robots (IOI13_robots)	C++14	100 / 100	2134 ms	24140 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));
    set<int>sr;
    int op=(int)small.size();
    int cnt[MAXN];
    memset(cnt,0,sizeof(cnt));
    for(int i=0;i<small.size();++i)
    {
        cnt[i]=moves;
        sr.insert(-i);
    }
    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
        {
            if(moves==1)cout<<query(MAXN-1)<<endl;
            used[i]=1;
            update(j,-1);
        }*/
        auto it=sr.lower_bound(s);
        if(it==sr.end())continue;
        used[i]=1;
        int val=(*it);
        --cnt[-val];
        if(cnt[-val]==0)sr.erase(val);
        --op;
        //if(moves==1)cout<<op<<endl;
    }
    int j=0;
    int cnt1=moves;
    vector<int>small_taken,weak_taken;
    for(int i=0;i<toys.size();++i)
    {
        /*if(moves==1)
        {
            if(used[i])
            {
                cout<<toys[i].w<<" "<<toys[i].s<<" S\n";
                small_taken.push_back(toys[i].s);
            }
            else
            {
                cout<<toys[i].w<<" "<<toys[i].s<<" W\n";
                weak_taken.push_back(toys[i].w);
            }
        }*/
        if(used[i])continue;
        if(j>=weak.size())return 0;
        if(cnt1==0&&j==weak.size()-1)return 0;
        if(cnt1==0)
        {
            cnt1=moves;
            ++j;
        }
        if(toys[i].w>weak[j])return 0;
        --cnt1;
    }
    /*if(moves==1)
    {
        sort(weak_taken.rbegin(),weak_taken.rend());
        sort(small_taken.rbegin(),small_taken.rend());
        if(weak_taken.size()>weak.size())cout<<"wtf1\n";
        if(small_taken.size()>small.size())cout<<"wtf2\n";
    }*/
    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());
    for(int i=0;i<toys.size();++i)
    {
        int low=0,high=weak.size()-1,mid,best=-1;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(weak[mid]>=toys[i].w)
            {
                best=mid;
                low=mid+1;
            }
            else high=mid-1;
        }
        if(best!=-1)toys[i].w=weak[best];
        else toys[i].w=2000000001;
    }
    sort(small.rbegin(),small.rend());
    for(int i=0;i<toys.size();++i)
    {
        int low=0,high=small.size()-1,mid,best=-1;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(small[mid]>=toys[i].s)
            {
                best=mid;
                low=mid+1;
            }
            else high=mid-1;
        }
        toys[i].s=-best;
    }
    sort(toys.rbegin(),toys.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:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<small.size();++i)
      |                 ~^~~~~~~~~~~~~
robots.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i=0;i<toys.size();++i)
      |                 ~^~~~~~~~~~~~
robots.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i=0;i<toys.size();++i)
      |                 ~^~~~~~~~~~~~
robots.cpp:104:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         if(j>=weak.size())return 0;
      |            ~^~~~~~~~~~~~~
robots.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         if(cnt1==0&&j==weak.size()-1)return 0;
      |                     ~^~~~~~~~~~~~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:132:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for(int i=0;i<toys.size();++i)
      |                 ~^~~~~~~~~~~~
robots.cpp:149:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for(int i=0;i<toys.size();++i)
      |                 ~^~~~~~~~~~~~

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