Submission #903625

#	Time	Username	Problem	Language	Result	Execution time	Memory
903625		Anorak2020	Robots (IOI13_robots)	C++17	0 / 100	3055 ms	4596 KiB

robots

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

using namespace std;
#define ll long long
#define F first
#define S second
mt19937 rnd(100);

int putaway(int N, int M, int K, int X0[], int Y0[], int PX[], int PY[]) {
    multiset<int> X, Y;
    for (int i = 0; i < N; i++)
        X.insert(X0[i] - 1);
    for (int i = 0; i < M; i++)
        Y.insert(Y0[i] - 1);

    for (int i = 0; i < K; i++)
        if (X.lower_bound(PX[i]) == X.end() && Y.lower_bound(PY[i]) == Y.end()) 
            return -1;
    
    map<int, multiset<pair<int, int>>*> ver, hor;
    for (int i = 0; i < K; i++)
    {
        int h = *X.lower_bound(PX[i]);
        if (!ver.count(h))
            ver[h] = new multiset<pair<int, int>>;
        ver[h]->insert({PY[i], PX[i]});

        h = *Y.lower_bound(PY[i]);
        if (!hor.count(h))
            hor[h] = new multiset<pair<int, int>>;
        hor[h]->insert({PX[i], PY[i]});
    }
    
    int ans = 0;
    while (K) {
        for (int x : X) { // Перебираем вертикальную прямую.
            auto p0 = ver.upper_bound(x);
            if (p0 == ver.begin())
                continue;
            --p0;
            pair<int, int> p = *prev(p0->S->end()); // Удаляемая пара (y x)
            p0->S->erase(p);
            if (p0->S->empty())
                ver.erase(p0);
            
            int h = *Y.lower_bound(p.F);
            if (!hor.count(h))
                hor[h] = new multiset<pair<int, int>>;
            hor[h]->erase({p.S, p.F});
            if (hor[h]->empty())
                hor.erase(h);
            K--;
        }

        for (int y : Y) {
            auto p0 = hor.upper_bound(y);
            if (p0 == hor.begin())
                continue;
            --p0;
            pair<int, int> p = *prev(p0->S->end()); // Удаляемая пара (x y)
            p0->S->erase(p);
            if (p0->S->empty())
                hor.erase(p0);
            
            int h = *X.lower_bound(p.F);
            if (!ver.count(h))
                ver[h] = new multiset<pair<int, int>>;
            ver[h]->erase({p.S, p.F});
            if (ver[h]->empty())
                ver.erase(h);
            K--;
        }

        ans++;
    }

    return ans;
}

/*int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    int N, M, K;
    cin >> N >> M >> K;
    int X[N], Y[M], PX[K], PY[K];
    for (int &i : X)
        cin >> i;
    for (int &i : Y)
        cin >> i;
    for (int i = 0; i < K; i++)
        cin >> PX[i] >> PY[i];
    
    cout << putaway(N, M, K, X, Y, PX, PY);
}*/
/*
3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5

2 1 3
2 5
3
3 1
5 3
2 2

*/
/*

*/
/*
Ох. Я конечно стер предыдущие большие мысли, но все еще выглядит как жадник.
Для каждой вертикальной прямой есть элементы которые находятся в самом правом доступном для этой прямой столбце.
Из них мы берем максимальный по другому параметру элемент.
Правда ли это? Подумаю над контр тестом.

Ладно. Можно сначала в тупую написать.

Можно максимально в тупую. Нужно идею проверить.

Для каждой точки найдем первую прямую справа.
Разделим точки по признаку такой прямой.
При обработке удаления от прямой, мы берем множество для самой правой из прямых левее и удаляем максимальную по второй координате точку оттуда.

Вопрос появился.
Важно ли для прямых одного типа то, как по ним проходиться?
Ну, вдруг да, будем проходиться снизу вверх.

*/
/*

*/
/*

*/
/*




*/
/*
10 _   _ | _   _   _   _ | _   _   _ | _

9  _   _ | _   _   _   _ | 3   _   _ | _

8  4   _ | _   _   _   _ | _   _   _ | _
  ---------------------------------------
7  _   _ | _   _   _   _ | _   7   _ | _

6  _   _ | _   0   _   _ | 8   _   _ | _

5  _   _ | _   _   _   _ | _   1   _ | 9
  ---------------------------------------
4  _   _ | _   _   _   _ | _   _   _ | _

3  _   2 | 6   _   _   _ | _   _   _ | _

2  _   _ | _   _   _   _ | _   _   _ | _

1  _   _ | _   _   5   _ | _   _   _ | _
   1   2   3   4   5   6   7   8   9   10





10 _   _ | _   _   _   _ | _   _   _ | _

9  _   _ | _   _   _   _ | _   _   _ | _

8  _   _ | _   _   _   _ | _   _   _ | _
  ---------------------------------------
7  _   _ | _   _   _   _ | _   7   _ | _

6  _   _ | _   _   _   _ | 8   _   _ | _

5  _   _ | _   _   _   _ | _   1   _ | _
  ---------------------------------------
4  _   _ | _   _   _   _ | _   _   _ | _

3  _   2 | _   _   _   _ | _   _   _ | _

2  _   _ | _   _   _   _ | _   _   _ | _

1  _   _ | _   _   5   _ | _   _   _ | _
   1   2   3   4   5   6   7   8   9   10





10 _   _ | _   _   _   _ | _   _   _ | _

9  _   _ | _   _   _   _ | _   _   _ | _

8  _   _ | _   _   _   _ | _   _   _ | _
  ---------------------------------------
7  _   _ | _   _   _   _ | _   _   _ | _

6  _   _ | _   _   _   _ | _   _   _ | _

5  _   _ | _   _   _   _ | _   1   _ | _
  ---------------------------------------
4  _   _ | _   _   _   _ | _   _   _ | _

3  _   _ | _   _   _   _ | _   _   _ | _

2  _   _ | _   _   _   _ | _   _   _ | _

1  _   _ | _   _   _   _ | _   _   _ | _
   1   2   3   4   5   6   7   8   9   10

*/

Compilation message (stderr)

robots.cpp:2:20: warning: extra tokens at end of #include directive
    2 | #include "robots.h".
      |                    ^

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