Submission #155382

#	Time	Username	Problem	Language	Result	Execution time	Memory
155382		arnold518	Robots (IOI13_robots)	C++14	0 / 100	254 ms	19436 KiB

robots

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e4;
const int MAXT = 1e6;

int A, B, T, *X, *Y, *W, *S;
pii toy[MAXT+10];
int cnt[MAXN+10];

bool decide(int x)
{
    int i, j;
    int left=0;
    for(i=A-1; i>=0; i--)
    {
        if(cnt[i]>x+left) return false;
        left=x+left-cnt[i];
    }
    return true;
}

int putaway(int _A, int _B, int _T, int *_X, int *_Y, int *_W, int *_S)
{
    int i, j;
    A=_A; B=_B; T=_T; X=_X; Y=_Y; W=_W; S=_S;
    for(i=0; i<T; i++) toy[i]={W[i], S[i]};
    sort(toy, toy+T);
    sort(X, X+A);
    sort(Y, Y+B);

    if(toy[T-1].first>=X[A-1]) return -1;

    int it=0;
    for(i=0; i<T; i++)
    {
        while(X[it]<=toy[i].first) it++;
        cnt[it]++;
    }

    int lo=0, hi=1e5;
    while(lo+1<hi)
    {
        int mid=lo+hi>>1;
        if(decide(mid)) hi=mid;
        else lo=mid;
    }
    return hi;
}

Compilation message (stderr)

robots.cpp: In function 'bool decide(int)':
robots.cpp:18:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:49:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=lo+hi>>1;
                 ~~^~~
robots.cpp:30:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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