Submission #903656

#	Time	Username	Problem	Language	Result	Execution time	Memory
903656		Anorak2020	Robots (IOI13_robots)	C++17	53 / 100	3085 ms	65536 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) {
        int bad = -1;
        for (int x : X) { // Перебираем вертикальную прямую.
            auto p0 = ver.upper_bound(x);
            if (p0 == ver.begin()) {
                bad = x;
                continue;
            }
            --p0;
            pair<int, int> p = *prev(p0->S->end()); // Удаляемая пара (y x)
            p0->S->erase(p0->S->find(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(hor[h]->find({p.S, p.F}));
            if (hor[h]->empty())
                hor.erase(h);
            K--;
        }

        while (!X.empty() && *X.begin() <= bad)
            X.erase(X.begin());

        bad = -1;
        for (int y : Y) {
            auto p0 = hor.upper_bound(y);
            if (p0 == hor.begin()) {
                bad = y;
                continue;
            }
            --p0;
            pair<int, int> p = *prev(p0->S->end()); // Удаляемая пара (x y)
            p0->S->erase(p0->S->find(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(ver[h]->find({p.S, p.F}));
            if (ver[h]->empty())
                ver.erase(h);
            K--;
        }

        while (!Y.empty() && *Y.begin() <= bad)
            Y.erase(Y.begin());

        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

1 1 3
100
100
1 1
1 1
1 1

*/
/*

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

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

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

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

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


Опа. Идея сработала.
Осталось оптимизировать.

Такс. У меня тлится на тестах с N == 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: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10