Submission #974973

#	Time	Username	Problem	Language	Result	Execution time	Memory
974973		n3rm1n	Robots (IOI13_robots)	C++17	100 / 100	2359 ms	48876 KiB

robots

#include<bits/stdc++.h>
#include"robots.h"
using namespace std;
const int MAXN = 1e6 + 10;
int a, b, tcnt, x[MAXN], y[MAXN], s[MAXN], w[MAXN];

int xt;
int fr[MAXN * 4], t[MAXN * 4];

struct toys
{
    int w, s, id;
    toys() {};
    toys(int _w, int _s, int _id)
    {
        w = _w;
        s = _s;
        id = _id;
    }
};
vector < toys > g;
bool cmp(toys t1, toys t2)
{
    if(t1.s != t2.s)return (t1.s > t2.s);
    if(t1.w != t2.w)return (t1.w > t2.w);
    return (t1.id < t2.id);
}
void make_tree(int i, int l, int r)
{
    if(l > r)return;
    if(l == r)
    {
        fr[l] = xt;
        t[i] = x[l];
        return;
    }
    int mid = (l + r)/2;
    make_tree(2*i, l, mid);
    make_tree(2*i+1, mid+1, r);
    t[i] = max(t[2*i], t[2*i+1]);
    //cout << l << " " << r << " " << t[i] << endl;
}
int wei, no = 0;
int query(int i, int l, int r)
{
    if(l > r)
    {
        no = 1;
        return 0;
    }
    if(l == r)
    {
        if(t[i] <= wei)no = 1;
        return l;
    }
    int mid = (l + r)/2;
    if(t[2*i] > wei)return query(2*i, l, mid);
    else return query(2*i+1, mid+1, r);
}
int indexx;
void update(int i, int l, int r)
{
    if(l > r)return;
    if(l == r)
    {
        fr[l] --;
        if(fr[l] == 0)t[i] = -1;
        else t[i] = x[l];
        return;
    }
    int mid = (l + r)/2;
    if(indexx <= mid)update(2*i, l, mid);
    else update(2*i+1, mid+1, r);
    t[i] = max(t[2*i], t[2*i+1]);
}
int marked[MAXN];
int usedy[MAXN];
bool check(int curr_xt)
{
    memset(marked, 0, sizeof(marked));
    xt = curr_xt;
    // cout << endl;
    // cout << xt << " is the time " << endl;
    // cout << endl;
    if(a != 0)
    {
        make_tree(1, 0, a-1);

        for (int i = 0; i < g.size(); ++ i)
        {
            int weight = g[i].w;
            no = 0;
            wei = weight;
            indexx = query(1, 0, a-1);
            //cout << weight << ", " << g[i].id << " is on " << indexx << endl;
            //cout << " but no = " << no << endl;
            if(no == 1)continue;
            update(1, 0, a-1);
            marked[g[i].id] = 1;
           // cout << g[i].id << endl;
        }
    }
    vector < int > u;
    for (int i = 0; i < tcnt; ++ i)
    {
        if(!marked[i])u.push_back(s[i]);
    }
    sort(u.begin(), u.end());
    /* for (int i = 0; i < u.size(); ++ i)
         cout << u[i] << " ";
     cout << endl;*/
    // cout << u.size() << endl;
    memset(usedy, 0, sizeof(usedy));
    int curr = 0;
    for (int i = 0; i < u.size(); ++ i)
    {
        while(curr < b && y[curr] <= u[i] || usedy[curr] == xt)curr ++;
        if(curr < b)
        {
            usedy[curr] ++;
        }
        else return false;
    }
    return true;
}



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

    for (int i = 0; i < T; ++ i)
    {
        s[i] = S[i];
        w[i] = W[i];
        g.push_back(toys(w[i], s[i], i));
    }

    sort(g.begin(), g.end(), cmp);

    /*for (int i = 0; i < g.size(); ++ i)
        cout << g[i].w << " ";
    cout << endl;
    for (int i = 0; i < g.size(); ++ i)
        cout << g[i].s << " ";
    cout << endl;
    for (int i = 0; i < g.size(); ++ i)
        cout << g[i].id << " ";
    cout << endl;*/
    for (int i = 0; i < A; ++ i)
        x[i] = X[i];
    for (int i = 0; i < B; ++ i)
        y[i] = Y[i];

    a = A;
    b = B;
    tcnt = T;

    int l = 1, r = tcnt, mid, ans = -1;
    while(l <= r)
    {
        mid = (l + r)/2;
        if(check(mid))
        {
            ans = mid;
            r = mid -1;
        }
        else l = mid + 1;
    }
    return ans;
}

Compilation message (stderr)

robots.cpp: In function 'bool check(int)':
robots.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toys>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int i = 0; i < g.size(); ++ i)
      |                         ~~^~~~~~~~~~
robots.cpp:115:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int i = 0; i < u.size(); ++ i)
      |                     ~~^~~~~~~~~~
robots.cpp:117:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  117 |         while(curr < b && y[curr] <= u[i] || usedy[curr] == xt)curr ++;

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