제출 #571303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
571303		Deepesson	Robots (IOI13_robots)	C++17	76 / 100	3068 ms	42208 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
#define MAX 505000
typedef std::pair<int,int> pii;
typedef std::pair<int,int*> pipo;
typedef std::pair<pii,int> ppi;
bool pego[MAX];
const int inf = 1e9;
struct SegTree {
    std::deque<ppi> tab[MAX*4];
    void update(int t,ppi k,int la=0,int ra=MAX-1,int pos=1){
        tab[pos].push_back(k);
        int m = (la+ra)/2;
        if(la==ra)return;
        if(t<=m)
            update(t,k,la,m,pos*2);
        else
            update(t,k,m+1,ra,(pos*2)+1);
    }
    void sortar(int la=0,int ra=MAX-1,int pos=1){
        std::sort(tab[pos].begin(),tab[pos].end());
        int m = (la+ra)/2;
        sortar(la,m,pos*2);
        sortar(m+1,ra,(pos*2)+1);
    }
    void limpa(int x){
        while(tab[x].size()&&pego[tab[x].front().second])tab[x].pop_front();
    }
    ppi query(int l,int r,int la=0,int ra=MAX-1,int pos=1){
        if(ra<l||la>r)return {{inf,inf},inf};
        if(la>=l&&ra<=r){
            limpa(pos);
            if(tab[pos].size())return tab[pos].front();
            return {{inf,inf},inf};
        }
        int m = (la+ra)/2;
        return std::min(query(l,r,la,m,pos*2),query(l,r,m+1,ra,(pos*2)+1));
    }
};
//SegTree grupoA,grupoB;
int putaway(int A,int B,int T,int _X[],int _Y[],int _W[],int _S[]){
    std::vector<int> X,Y,W,S;
    for(int i=0;i!=A;++i){
        X.push_back(_X[i]);
    }
    for(int i=0;i!=B;++i){
        Y.push_back(_Y[i]);
    }
    for(int i=0;i!=T;++i){
        W.push_back(_W[i]);
        S.push_back(_S[i]);
    }

    {
        std::vector<pipo> vec;
        for(auto&x:X){
            vec.push_back({x,&x});
        }
        for(auto&x:Y){
            vec.push_back({x,&x});
        }
        for(auto&x:W){
            vec.push_back({x,&x});
        }
        for(auto&x:S){
            vec.push_back({x,&x});
        }
        std::sort(vec.begin(),vec.end());
        int cur=2,last=-(1e9);
        for(auto&x:vec){
            if(x.first!=last){
                ++cur;
                last=x.first;
            }
            *x.second=cur;
        }
    }

    std::sort(X.begin(),X.end());
    std::sort(Y.begin(),Y.end());
    int pesos[T]={};
    {
        std::vector<pii> vec;
        ///T itens
        for(int i=0;i!=T;++i){
            vec.push_back({W[i],i});
        }
        std::sort(vec.begin(),vec.end());
        ///A robos
        int soma[T]={};
        int cur=0;
        for(int i=0;i!=A;++i){
            while(cur!=T&&(vec[cur].first<X[i])){
                ++cur;
            }
            if(cur){
                soma[cur-1]++;
            }
        }
        int s=0;
        for(int i=T-1;i!=-1;--i){
            s+=soma[i];
            pesos[vec[i].second]+=s;
        }
    }
    {
        std::vector<pii> vec;
        ///T itens
        for(int i=0;i!=T;++i){
            vec.push_back({S[i],i});
        }
        std::sort(vec.begin(),vec.end());
        ///A robos
        int soma[T]={};
        int cur=0;
        for(int i=0;i!=B;++i){
            while(cur!=T&&(vec[cur].first<Y[i])){
                ++cur;
            }
            if(cur){
                soma[cur-1]++;
            }
        }
        int s=0;
        for(int i=T-1;i!=-1;--i){
            s+=soma[i];
            pesos[vec[i].second]+=s;
        }
    }
    for(auto&x:pesos)if(!x)return -1;
    int count=0,retirou=0;
    bool pegou[T]={};
    for(;;){
        ++count;
        std::vector<int> novA;
        for(int i=0;i!=X.size();++i){
            int pos=-1,valor = 1e9;
            for(int j=0;j!=T;++j){
                if(pegou[j])continue;
                if(W[j]<X[i]){
                    if(pesos[j]<valor){
                        valor=pesos[j];
                        pos=j;
                    }
                }
            }
            if(pos!=-1){
                pegou[pos]=true;
                ++retirou;
                novA.push_back(X[i]);
            }
        }
        X=novA;
        std::vector<int> novB;
        for(int i=0;i!=Y.size();++i){
            int pos=-1,valor=1e9;
            for(int j=0;j!=T;++j){
                if(pegou[j])continue;
                if(S[j]<Y[i]){
                    if(pesos[j]<valor){
                        valor=pesos[j];
                        pos=j;
                    }
                }
            }
            if(pos!=-1){
                pegou[pos]=true;
                novB.push_back(Y[i]);
                ++retirou;
            }
        }
        Y=novB;
        if(retirou==T){
            break;
        }
    }
    return count;
}

컴파일 시 표준 에러 (stderr) 메시지

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:136:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         for(int i=0;i!=X.size();++i){
      |                     ~^~~~~~~~~~
robots.cpp:155:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         for(int i=0;i!=Y.size();++i){
      |                     ~^~~~~~~~~~

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