Submission #98807

#	Time	Username	Problem	Language	Result	Execution time	Memory
98807		Alexa2001	Robots (IOI13_robots)	C++17	90 / 100	3084 ms	22516 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 50005, Mmax = 1e6 + 5;

int x[Mmax], y[Mmax];

class AIB
{
    int n, a[Nmax];
    int ub(int x) { return (x&(-x)); }
public:
    void set_size(int N) { n = N + 1; }

    int query(int x)
    {
        int ans = 0;
        for(++x; x; x-=ub(x)) ans += a[x];
        return ans;
    }

    void update(int x)
    {
        for(++x; x <= n; x+=ub(x)) a[x]++;
    }
} aib;


int cbin(int a[], int n, int x)
{
    int st = 0, dr = n - 1, mid;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(a[mid] > x) st = mid+1;
            else dr = mid-1;
    }
    return dr + 1;
}

bool cmp(int a, int b)
{
    if(x[a] == x[b]) return y[a] < y[b];
    return x[a] < x[b];
}

int upp(int x, int y) { if(x % y) return x / y + 1; return x / y; }

int putaway(int A, int B, int N, int W[], int S[], int X[], int Y[])
{
    int i;
    sort(W, W+A); reverse(W, W+A);
    sort(S, S+B); reverse(S, S+B);

    for(i=0; i<N; ++i)
    {
        x[i] = cbin(W, A, X[i]);
        y[i] = cbin(S, B, Y[i]);

        if(x[i] == 0 && y[i] == 0) return -1;
    }

    vector<int> ord;
    for(i=0; i<N; ++i) ord.push_back(i);
    sort(ord.begin(), ord.end(), cmp);

    int ans = 0, pos, j, k = 0;
    /*
    aib.set_size(B);
    for(i=0; i<ord.size(); ++i)
    {
        pos = ord[i];
        aib.update(y[pos]);

        if(i + 1 < ord.size() && x[pos] == x[ord[i+1]] && y[pos] == y[ord[i+1]]) continue;

        int act = aib.query(y[pos]);
        ans = max(ans, upp(act, x[pos] + y[pos]));
    }*/

    aib.set_size(B);
    for(i=0; i<=A; ++i)
        for(j=0; j<=B; ++j)
        {
            while(k < ord.size() && x[ord[k]] <= i && y[ord[k]] <= j) aib.update(y[ord[k]]), k++;

            if(i == 0 && j == 0) continue;

            int act = aib.query(j);
            ans = max(ans, upp(act, i + j));
        }

    return ans;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:87:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(k < ord.size() && x[ord[k]] <= i && y[ord[k]] <= j) aib.update(y[ord[k]]), k++;
                   ~~^~~~~~~~~~~~
robots.cpp:69:18: warning: unused variable 'pos' [-Wunused-variable]
     int ans = 0, pos, j, k = 0;
                  ^~~

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