oj.uz

답안 #962706

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
962706 2024-04-14T07:19:27 Z danikoynov 로봇 (IOI13_robots) C++14
76 / 100
 3000 ms 52632 KB 
#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxt = 1e6 + 10;
const int maxn = 1e5 + 10;

struct toy
{
    int w, s, idx;

    toy(int _w = 0, int _s = 0, int _idx = 0)
    {
        w = _w;
        s = _s;
    }
} toys[maxt];

bool cmp_w(toy t1, toy  t2)
{
    return t1.w < t2.w;
}

bool cmp_s(toy t1, toy t2)
{
    return t1.s < t2.s;
}

int x[maxn], y[maxn], used[maxt];
int a, b, t;


int cnt[maxn];

struct node
{
    int pos, mx;

    node (int _pos = -1, int _mx = -1)
    {
        pos = _pos;
        mx = _mx;
    }
};

node merge_node(node lf, node rf)
{
    if (lf.mx > rf.mx)
        return lf;
    return rf;
}

node tree[4 * maxt];
void build(int root, int left, int right)
{
    if (left == right)
    {
        tree[root].mx = toys[left].s;
        tree[root].pos = left;
        return;
    }

    int mid = (left + right) / 2;
    build(root * 2, left, mid);
    build(root * 2 + 1, mid + 1, right);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

void update(int root, int left, int right, int pivot)
{
    if (left == right)
    {
        tree[root].mx = -1;
        tree[root].pos = left;
        return;
    }

    int mid = (left + right) / 2;
    if (pivot <= mid)
        update(root * 2, left, mid, pivot);
    else
        update(root * 2 + 1, mid + 1, right, pivot);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

node query(int root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft)
        return node();

    if (left >= qleft && right <= qright)
        return tree[root];

    int mid = (left + right) / 2;
    return merge_node(query(root * 2, left, mid, qleft, qright),
                      query(root * 2 + 1, mid + 1, right, qleft, qright));
}


int to_x[maxn], stock[maxn];

int par[maxn];

int find_leader(int v)
{
    if (v == par[v])
        return v;
    return (par[v] = find_leader(par[v]));
}

int to_y[maxn];
bool check(int p)
{

    for (int i = 0; i <= a; i ++)
        par[i] = i, stock[i] = p;
    vector < toy > vec;
    for (int i = t - 1; i >= 0; i --)
    {
        int tk = find_leader(to_x[i]);
        while(tk < a && stock[tk] == 0)
          tk ++;
        if (tk == a)
          vec.push_back(toys[i]);
        else
        {
             stock[tk] --;
        }
        /**if (tk == a)
        {
            vec.push_back(toys[i]);
        }
        else
        {
            stock[tk] --;
            if (stock[tk] == 0)
                par[tk] = tk + 1;
        }*/
    }


    reverse(vec.begin(), vec.end());

    for (int i = 0; i < b; i ++)
        cnt[i] = 0;
    int pivot = 0;
    for (toy cur : vec)
    {
        while(pivot < b && (cur.s >= y[pivot] || cnt[pivot] == p))
            pivot ++;
        if (pivot == b)
            return false;
        cnt[pivot] ++;
    }

    return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    a = A;
    b = B;
    t = T;

    for (int i = 0; i < T; i ++)
    {
        toys[i] = toy(W[i], S[i]);
    }

    for (int i = 0; i < a; i ++)
        x[i] = X[i];
    for (int i = 0; i < b; i ++)
        y[i] = Y[i];


    sort(x, x + A);
    sort(y, y + B);
    sort(toys, toys + T, cmp_w);


    for (int i = 0; i < T; i ++)
        toys[i].idx = i;



    sort(toys, toys + T, cmp_s);
    for (int i = 0; i < t; i ++)
    {
        int lf = 0, rf = a - 1;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (x[mf] > toys[i].w)
                rf = mf - 1;
            else
                lf = mf + 1;
        }
        to_x[i] = lf;
    }
    int lf = 0, rf = T;
    while(lf <= rf)
    {

        int mf = (lf + rf) / 2;
        if (check(mf))
            rf = mf - 1;
        else
            lf = mf + 1;
    }

    if (lf > T)
        return - 1;
    return lf;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 52060 KB Output is correct
2 Correct 9 ms 52060 KB Output is correct
3 Correct 13 ms 52060 KB Output is correct
4 Correct 10 ms 52060 KB Output is correct
5 Correct 10 ms 52176 KB Output is correct
6 Correct 11 ms 52180 KB Output is correct
7 Correct 24 ms 45984 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 52056 KB Output is correct
2 Correct 10 ms 52060 KB Output is correct
3 Correct 14 ms 46172 KB Output is correct
4 Execution timed out 3089 ms 50208 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 46028 KB Output is correct
2 Correct 14 ms 46172 KB Output is correct
3 Correct 10 ms 52172 KB Output is correct
4 Correct 10 ms 52312 KB Output is correct
5 Correct 12 ms 45916 KB Output is correct
6 Correct 17 ms 46012 KB Output is correct
7 Correct 10 ms 52056 KB Output is correct
8 Correct 9 ms 52144 KB Output is correct
9 Correct 15 ms 45916 KB Output is correct
10 Correct 10 ms 52060 KB Output is correct
11 Correct 12 ms 52056 KB Output is correct
12 Correct 12 ms 52060 KB Output is correct
13 Correct 11 ms 52184 KB Output is correct
14 Correct 10 ms 52120 KB Output is correct

Subtask #4
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 46016 KB Output is correct
2 Correct 14 ms 45916 KB Output is correct
3 Correct 12 ms 46096 KB Output is correct
4 Correct 15 ms 52060 KB Output is correct
5 Correct 13 ms 52060 KB Output is correct
6 Correct 12 ms 46168 KB Output is correct
7 Correct 9 ms 52060 KB Output is correct
8 Correct 10 ms 52060 KB Output is correct
9 Correct 12 ms 45916 KB Output is correct
10 Correct 12 ms 46172 KB Output is correct
11 Correct 13 ms 46112 KB Output is correct
12 Correct 11 ms 46168 KB Output is correct
13 Correct 9 ms 52204 KB Output is correct
14 Correct 10 ms 52060 KB Output is correct
15 Correct 11 ms 46168 KB Output is correct
16 Correct 19 ms 46264 KB Output is correct
17 Correct 19 ms 46408 KB Output is correct
18 Correct 22 ms 46428 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 52060 KB Output is correct
2 Correct 10 ms 46020 KB Output is correct
3 Correct 10 ms 46016 KB Output is correct
4 Correct 10 ms 45916 KB Output is correct
5 Correct 10 ms 52060 KB Output is correct
6 Correct 10 ms 52060 KB Output is correct
7 Correct 17 ms 46172 KB Output is correct
8 Correct 10 ms 52056 KB Output is correct
9 Correct 11 ms 52188 KB Output is correct
10 Execution timed out 3055 ms 52632 KB Time limit exceeded
11 Halted 0 ms 0 KB -