Submission #578987

#	Time	Username	Problem	Language	Result	Execution time	Memory
578987		enerelt14	Robots (IOI13_robots)	C++17	0 / 100	9 ms	14036 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
int a, b, t;
vector<int>bb[500005];
int num[500005];
int bs[500005];
bool solve(int s){
    memset(num, 0, sizeof(num));
    for (int i=0;i<a;i++){
    	if (bs[i]>s)return 0;
        if (bb[i].size()<=s-bs[i])continue;
        if (b==0)return 0;
        for (int j=0;j<bb[i].size()-s+bs[i];j++){
            num[bb[i][j]]++;
        }
    }
    for (int i=0;i<bb[a].size();i++)num[bb[a][i]]++;
    long long cur=0;
    for (int i=b-1;i>=0;i--){
        cur+=num[i];
        if (cur>1LL*s*(b-i))return 0;
    }
    return 1;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
    for (int i=0;i<=A;i++)bb[i].clear();
    sort(X, X+A);
	sort(Y, Y+B);
    int x, y;
    for (int i=0;i<T;i++){
        int l=0, r=A-1;
        while(true){
        	if (l>r)break;
            if (l==r){
                if (X[l]<=W[i])x=l+1;
                else x=l;
                break;
            }
            int mid=(l+r)/2;
            if (X[mid+1]<=W[i])l=mid+1;
            else r=mid;
        }
        l=0;r=B-1;
        while(true){
        	if (l>r)break;
            if (l==r){
                if (Y[l]<=S[i])y=l+1;
                else y=l;
                break;
            }
            int mid=(l+r)/2;
            if (Y[mid+1]<=S[i])l=mid+1;
            else r=mid;
        }
        if (A==0)x=0;
        if (B==0)y=0;
        if (x==A && y==B)return -1;
        if (y!=B || B==0)bb[x].push_back(y);
        else bs[x]++;
    }
    a=A;
    b=B;
    t=T;
    for (int i=0;i<=a;i++){
        sort(bb[i].begin(), bb[i].end());
    }
    int l=1, r=T;
    while(true){
        if (l==r)return l;
        int mid=(l+r)/2;
        if (solve(mid))r=mid;
        else l=mid+1;
    }
}

Compilation message (stderr)

robots.cpp: In function 'bool solve(int)':
robots.cpp:14:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   14 |         if (bb[i].size()<=s-bs[i])continue;
      |             ~~~~~~~~~~~~^~~~~~~~~
robots.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for (int j=0;j<bb[i].size()-s+bs[i];j++){
      |                      ~^~~~~~~~~~~~~~~~~~~~~
robots.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i=0;i<bb[a].size();i++)num[bb[a][i]]++;
      |                  ~^~~~~~~~~~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:61:9: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |         if (x==A && y==B)return -1;
      |         ^~

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