Submission #993317

#	Time	Username	Problem	Language	Result	Execution time	Memory
993317		MrDeboo	Robots (IOI13_robots)	C++17	76 / 100	3101 ms	61020 KiB

robots

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include "robots.h"
#include "bits/stdc++.h"
using namespace std;
vector<pair<int,int>>v;
int mid;
deque<int>a,b;
map<pair<int,int>,int>mp;
bool bol;
bool slv(){
    if(!bol){
        priority_queue<pair<int,int>>pq;
        int l=0;
        for(int i=0;i<a.size();i++){
            while(l<v.size()&&a[i]>v[l].first){
                if(bol&&mp[v[l]])mp[v[l]]--;
                else pq.push({v[l].second,v[l].first});
                l++;
            }
            int k=mid;
            while(pq.size()&&k--){
                if(!bol)mp[pq.top()]++;
                pq.pop();
            }
        }
        while(l<v.size()){
            if(bol&&mp[v[l]])mp[v[l]]--;
            else pq.push({v[l].second,v[l].first});
            l++;
        }
        return pq.empty();
    }
    int g=0;
    int l=0;
    for(int i=0;i<a.size();i++){
        while(l<v.size()&&a[i]>v[l].first){
            if(bol&&mp[v[l]])mp[v[l]]--;
            else g++;
            l++;
        }
        int k=mid;
        g=max(0,g-k);
    }
    while(l<v.size()&&g==0){
        if(bol&&mp[v[l]])mp[v[l]]--;
        else g++;;
        l++;
    }
    return g==0;
}
int putaway(int A, int B, int t, int x[], int y[], int w[], int s[]) {
    if(A<B){
        swap(A,B);
        swap(x,y);
        swap(w,s);
    }
    for(int i=0;i<t;i++)v.push_back({w[i],s[i]});
    for(int i=0;i<A;i++)a.push_back(x[i]);
    for(int i=0;i<B;i++)b.push_back(y[i]);
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int l=1,r=t,f=-1;
    vector<pair<int,int>>vec=v;
    sort(vec.begin(),vec.end());
    vector<pair<int,int>>vec2=v;
    for(auto &i:vec2)swap(i.first,i.second);
    sort(vec2.begin(),vec2.end());
    while(l<=r){
        mid=(l+r)/2;
        swap(v,vec);
            mp.clear();
            bol=0;
            slv();
            swap(v,vec);
            bol=1;
            v=vec2;
            swap(a,b);
            swap(v,vec2);
            bool bl=slv();
            swap(v,vec2);
            swap(a,b);
            if(bl){
                r=mid-1;
                f=mid;
            }else l=mid+1;

    }
    return f;
}

Compilation message (stderr)

robots.cpp: In function 'bool slv()':
robots.cpp:15:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         for(int i=0;i<a.size();i++){
      |                     ~^~~~~~~~~
robots.cpp:16:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |             while(l<v.size()&&a[i]>v[l].first){
      |                   ~^~~~~~~~~
robots.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         while(l<v.size()){
      |               ~^~~~~~~~~
robots.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~
robots.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         while(l<v.size()&&a[i]>v[l].first){
      |               ~^~~~~~~~~
robots.cpp:45:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while(l<v.size()&&g==0){
      |           ~^~~~~~~~~

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