Submission #1039182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039182		Hugo1729	Robots (IOI13_robots)	C++11	90 / 100	1518 ms	65536 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;

int A, B, T, X[50000], Y[50000];
pair<int,int> Z[1000000];

int sz=1;
int t[4000000];

void get_input(int _A, int _B, int _T, int _X[], int _Y[], int _W[], int _S[]){
    A=_A;
    B=_B;
    T=_T;

    vector<int> weights, sizes;
    for(int i=0;i<A;i++)weights.push_back(_X[i]);
    for(int i=0;i<B;i++)sizes.push_back(_Y[i]);
    for(int i=0;i<T;i++)weights.push_back(_W[i]);
    for(int i=0;i<T;i++)sizes.push_back(_S[i]);

    sort(weights.begin(),weights.end());
    sort(sizes.begin(),sizes.end());

    map<int,int> msizes,mweights;

    int cntw=1,cnts=1;

    for(int w : weights){
        if(!mweights.count(w))mweights[w]=cntw++;
    }
    for(int s : sizes){
        if(!msizes.count(s))msizes[s]=cnts++;
    }

    for(int i=0;i<A;i++)X[i]=mweights[_X[i]];
    for(int i=0;i<B;i++)Y[i]=msizes[_Y[i]];
    for(int i=0;i<T;i++)Z[i]={mweights[_W[i]],msizes[_S[i]]};

    sort(Z,Z+T);
    sort(X,X+A);
    sort(Y,Y+B);

    // for(int i=0;i<A;i++)cout << X[i] << ' ';
    // cout << '\n';
    // for(int i=0;i<B;i++)cout << Y[i] << ' ';
    // cout << '\n';
    // for(int i=0;i<T;i++)cout <<'(' <<  Z[i].first << ' ' << Z[i].second << ") ";
    // cout << '\n';

    while(sz<T)sz<<=1;
}

void build(int v, int tl, int tr, vector<int>& a){
    if(tl==tr)t[v]=a[v-sz];
    else{
        int mid=(tl+tr)/2;
        build(2*v, tl, mid,a);
        build(2*v+1,mid+1, tr, a);
        t[v]=min(t[v*2],t[v*2+1]);
    }
}

void update(int k, int val){
    k+=sz-1;
    t[k]=val;
    for(k>>=1;k>0;k>>=1)t[k]=min(t[k*2],t[k*2+1]);
}

int find(int val){
    if(t[1]>=val)return 0;
    int v=1;
    while(v<sz){
        if(t[v*2+1]<val)v=v*2+1;
        else v=v*2;
    }

    return v-sz+1;
}

bool check(int d){

    vector<int> temp(sz,INT32_MAX);
    for(int i=0;i<T;i++)temp[i]=Z[i].second;

    build(1,1,sz,temp);

    for(int i=0;i<B;i++){
        for(int j=0;j<d;j++){
            int index=find(Y[i]);
            if(!index)break;

            update(index,INT32_MAX);
        }
    }

    vector<int> rest;
    for(int i=0;i<T;i++){
        if(t[i+sz]!=INT32_MAX){
            rest.push_back(Z[i].first);
        }
    }

    sort(rest.begin(),rest.end());

    int ptr=0;

    for(int i=0;i<A;i++){
        if(ptr==rest.size())break;
        for(int j=0;j<d;j++){
            if(ptr==rest.size())break;
            if(X[i]>rest[ptr])ptr++;
            else break;
        }
    }

    if(ptr==rest.size())return 1;
    else return 0;





    // for(int i=0;i<A;i++)cout << X[i] << ' ';
    // cout << '\n';
    // for(int i=0;i<B;i++)cout << Y[i] << ' ';
    // cout << '\n';
    // for(int i=0;i<T;i++)cout <<'(' <<  Z[i].first << ' ' << Z[i].second << ") ";
    // cout << '\n';
}






int putaway(int _A, int _B, int _T, int _X[], int _Y[], int _W[], int _S[]) {

    get_input(_A, _B, _T, _X, _Y, _W, _S);

    int lo=1, hi=T;

    if(!check(hi))return -1;
    else if(check(lo))return lo;

    while(lo<hi-1){
        int mid=(lo+hi)/2;
        if(check(mid))hi=mid;
        else lo=mid;
    }
    return hi;
}

Compilation message (stderr)

robots.cpp: In function 'bool check(int)':
robots.cpp:109:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         if(ptr==rest.size())break;
      |            ~~~^~~~~~~~~~~~~
robots.cpp:111:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             if(ptr==rest.size())break;
      |                ~~~^~~~~~~~~~~~~
robots.cpp:117:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     if(ptr==rest.size())return 1;
      |        ~~~^~~~~~~~~~~~~

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