Submission #155387

#	Time	Username	Problem	Language	Result	Execution time	Memory
155387		arnold518	Robots (IOI13_robots)	C++14	0 / 100	255 ms	17016 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;
    ll left=0;
    for(i=A; i>=1; 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=1; i<=T; i++) toy[i]={W[i-1], S[i-1]};
    for(i=A; i>=1; i--) X[i]=X[i-1];
    for(i=B; i>=1; i--) Y[i]=Y[i-1];

    sort(toy+1, toy+T+1);
    sort(X+1, X+A+1);
    sort(Y+1, Y+B+1);

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

    int lo=0, hi=1e6;
    while(lo+1<hi)
    {
        int mid=lo+hi>>1;
        if(decide(mid)) hi=mid;
        else lo=mid;
    }
    if(hi==1e6) return -1;
    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:50: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