Submission #589470

#	Time	Username	Problem	Language	Result	Execution time	Memory
589470		ogibogi2004	Robots (IOI13_robots)	C++14	0 / 100	3 ms	5204 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)
{
    cout<<"?\n";
    memset(used,0,sizeof(used));
    memset(fen,0,sizeof(fen));
    for(int i=0;i<small.size();i++)update(i,moves);
    multiset<pair<int,int> >sr;
    int op=(int)small.size();
    for(int i=0;i<small.size();i++)sr.insert({small[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
        {
            if(moves==1)cout<<query(MAXN-1)<<endl;
            used[i]=1;
            update(j,-1);
        }*/
        auto it=sr.lower_bound({s,-1});
        if(it==sr.end())continue;
        used[i]=1;
        int val=(*it).first,cnt=(*it).second;
        sr.erase(sr.find({val,cnt}));
        cnt--;
        if(cnt>0)sr.insert({val,cnt});
        op--;
        //if(moves==1)cout<<op<<endl;
    }
    int cnt=moves,j=0;
    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(cnt==0&&j==weak.size()-1)return 0;
        if(cnt==0)
        {
            cnt=moves;
            j++;
        }
        if(toys[i].w>weak[j])return 0;
        cnt--;
    }
    /*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(toys.rbegin(),toys.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:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i<small.size();i++)update(i,moves);
      |                 ~^~~~~~~~~~~~~
robots.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<small.size();i++)sr.insert({small[i],moves});
      |                 ~^~~~~~~~~~~~~
robots.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i=0;i<toys.size();i++)
      |                 ~^~~~~~~~~~~~
robots.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i=0;i<toys.size();i++)
      |                 ~^~~~~~~~~~~~
robots.cpp:101:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         if(j>=weak.size())return 0;
      |            ~^~~~~~~~~~~~~
robots.cpp:102:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         if(cnt==0&&j==weak.size()-1)return 0;
      |                    ~^~~~~~~~~~~~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:129:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for(int i=0;i<toys.size();i++)
      |                 ~^~~~~~~~~~~~

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