Submission #852745

#	Time	Username	Problem	Language	Result	Execution time	Memory
852745		danikoynov	IOI Fever (JOI21_fever)	C++14	0 / 100	1 ms	600 KiB

fever

/**
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const int maxn = 3010;
const int inf = 2e9;
struct point
{
    int x, y;
} p[maxn];

int n, used[maxn], dir[maxn];
/**
directions:
0 - north
1 - east
2 - south
3 - west
*/

struct collision
{
    int idx1, idx2, tp;

    collision(int _idx1, int _idx2, int _tp)
    {
        idx1 = _idx1;
        idx2 = _idx2;
        tp = _tp;
    }

    bool operator < (const collision &c) const
    {
        if (tp != c.tp)
            return tp < c.tp;

        if (min(idx2, idx1) != min(c.idx1, c.idx2))
            return min(idx2, idx1) < min(c.idx1, c.idx2);

        return max(idx1, idx2 ) < max(c.idx1, c.idx2);

    }
};

bool cmp(collision c1, collision c2)
{
    return c1.tp < c2.tp;
}

unordered_map < int, set < pair < int, int > > > mdig[4], fdig[4];
set < collision > event;

int get_collision_time(int i, int j)
{
    if (p[i].x == p[j].x)
    {
        return abs(p[j].y - p[i].y);
    }
    if (p[i].y == p[j].y)
    {
        return abs(p[i].x - p[j].x);
    }

    return 2 * abs(p[i].x - p[j].x);
}
void get_next_collsion(int id)
{
    int md = p[id].y - p[id].x;
    int fd = p[id].x + p[id].y;
    collision nxt(0,0, inf);
    set < pair < int, int > > :: iterator it;
    if (dir[id] == 0)
    {
        it = mdig[3][md].lower_bound({p[id].x, -1});
        if (it != mdig[3][md].end())
        {
            collision cur(id, it -> second, get_collision_time(id, it -> second));
            nxt = min(nxt, cur);
        }

        it = fdig[1][fd].lower_bound({p[id].x, -1});
        if (it != fdig[1][fd].begin())
        {
            it = prev(it);
            collision cur(id, it -> second, get_collision_time(id, it -> second));
            nxt = min(nxt, cur);
        }
    }

    if (dir[id] == 1)
    {
        it = mdig[2][md].lower_bound({p[id].x, - 1});
        if (it != mdig[2][md].end())
        {
            collision cur(id, it -> second, get_collision_time(id, it -> second));
            nxt = min(nxt, cur);
        }

        it = fdig[0][fd].lower_bound({p[id].x, -1});
        if (it != fdig[0][fd].end())
        {
            collision cur(id, it -> second, get_collision_time(id, it -> second));
            nxt = min(nxt, cur);
        }
    }

    if (dir[id] == 2)
    {
        it = mdig[1][md].lower_bound({p[id].x, -1});
        if (it != mdig[1][md].begin())
        {
            it = prev(it);
            collision cur(id, it -> second, get_collision_time(id, it -> second));
            nxt = min(nxt, cur);
        }

        it = fdig[3][fd].lower_bound({p[id].x, -1});
        if (it != fdig[3][fd].end())
        {
            collision cur(id, it -> second, get_collision_time(id, it -> second));
            nxt = min(nxt, cur);
        }
    }

    if (dir[id] == 3)
    {
        it = mdig[0][md].lower_bound({p[id].x, -1});
        if (it != mdig[0][md].begin())
        {
            it = prev(it);
            collision cur(id, it -> second, get_collision_time(id, it -> second));
            nxt = min(nxt, cur);
        }


        it = fdig[2][fd].lower_bound({p[id].x, -1});
        if (it != fdig[2][fd].begin())
        {
            it = prev(it);
            collision cur(id, it -> second, get_collision_time(id, it -> second));
            nxt = min(nxt, cur);
        }
    }


    if (nxt.tp != inf)
        event.insert(nxt);
}

void add_point(int i)
{
        mdig[dir[i]][p[i].y - p[i].x].insert({p[i].x, i});
        fdig[dir[i]][p[i].y + p[i].x].insert({p[i].x, i});
}

void rem_point(int i)
{
        mdig[dir[i]][p[i].y - p[i].x].erase({p[i].x, i});
        fdig[dir[i]][p[i].y + p[i].x].erase({p[i].x, i});
}
int simulate()
{
    for (int i = 0; i < 4; i ++)
    {
        mdig[i].clear();
        fdig[i].clear();
    }
    event.clear();
    dir[1] = 1;
    for (int i = 2; i <= n; i ++)
    {

        if (p[i].x > 0 && p[i].y > 0)
        {
            if (p[i].x > p[i].y)
                dir[i] = 3;
            else
                dir[i] = 2;
        }
        else if (p[i].x > 0 && p[i].y < 0)
        {
            if (p[i].x > abs(p[i].y))
                dir[i] = 3;
            else
                dir[i] = 0;
        }
        else if (p[i].x < 0 && p[i].y > 0)
        {
            if (abs(p[i].x) < p[i].y)
                dir[i] = 2;
            else
                dir[i] = 1;
        }
        else if (p[i].x < 0 && p[i].y < 0)
        {
            if (abs(p[i].x) < abs(p[i].y))
                dir[i] = 0;
            else
                dir[i] = 1;
        }
        else
        {
            if (p[i].x == 0)
            {
                if (p[i].y > 0)
                    dir[i] = 2;
                else
                    dir[i] = 0;
            }
            else
            {
                if (p[i].x > 0)
                    dir[i] = 3;
                else
                    dir[i] = 1;
            }
        }
        add_point(i);

    }


    for (int i = 1; i <= n; i ++)
    {
        used[i] = 0;
    }
    used[1] = 1;
    get_next_collsion(1);
    int ans = 1;
    while(!event.empty())
    {
        collision cur = *event.begin();
        event.erase(event.begin());
        if (used[cur.idx1] == 1 && used[cur.idx2] == 1)
            continue;
        ans ++;
        used[cur.idx2] = 1;
        assert(used[cur.idx1] == 1);
        rem_point(cur.idx2);
        get_next_collsion(cur.idx1);
        get_next_collsion(cur.idx2);
    }

    ///cout << ans << endl;
    return ans;
    /**cout << "simulate " << endl;
    for (int i = 1; i <= n; i ++)
        cout << p[i].x << " " << p[i].y << " " << dir[i] << endl;*/

    /**for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
        {

            if (i == j || p[i].x > p[j].x)
                continue;
            if (p[i].x == p[j].x)
            {
                if (p[i].y > p[j].y)
                    continue;
                collision col(i, j, abs(p[i].y - p[j].y));
                if (dir[i] == 0 && dir[j] == 2)
                    event.push_back(col);
                continue;
            }
            if (p[i].y == p[j].y)
            {
                collision col(i, j, p[j].x - p[i].x);
                if (dir[i] == 1 && dir[j] == 3)
                    event.push_back(col);
                continue;
            }

            if (((p[i].y - p[i].x) != (p[j].y - p[j].x)) &&
                    ((p[i].y + p[i].x) != (p[j].y + p[j].x)))
                continue;
            ///cout << "test " << i << " " << j << endl;
            collision col(i, j, (int)(abs(p[i].x - p[j].x)) * 2);
            if (p[i].y < p[j].y)
            {
                if ((dir[i] == 1 && dir[j] == 2) ||
                        ((dir[i] == 0 && dir[j] == 3)))
                    event.push_back(col);
            }
            else if (p[i].y > p[j].y)
            {
                if ((dir[i] == 1 && dir[j] == 0) ||
                        (dir[i] == 2 && dir[j] == 3))
                    event.push_back(col);
            }

        }
    ///exit(0);
    sort(event.begin(), event.end(), cmp);
    for (int i = 1; i <= n; i ++)
        used[i] = 0;
    used[1] = 1;
    for (collision cur : event)
    {
        ///cout << "collision " << cur.idx1 << " " << cur.idx2 << " " << cur.tp << endl;
        int cx = max(used[cur.idx1], used[cur.idx2]);
        used[cur.idx1] = cx;
        used[cur.idx2] = cx;
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++)
        cnt += used[i];

    return cnt;*/
}

void perform90()
{
    for (int i = 1; i <= n; i ++)
    {
        int nx = p[i].y, ny = - p[i].x;
        p[i].x = nx;
        p[i].y = ny;
    }
}


void solve()
{
    cin >> n;

    for (int i = 1; i <= n; i ++)
    {
        cin >> p[i].x >> p[i].y;
        if (i != 1)
        {
            p[i].x -= p[1].x;
            p[i].y -= p[1].y;
        }
    }
    p[1].x = p[1].y = 0;


    int ans = 0;
    for (int d = 0; d < 4; d ++)
    {
        ans = max(ans, simulate());
        perform90();
    }

    cout << ans << endl;

}

int main()
{
    solve();
    return 0;
}
/**
7
64 52
68 56
65 53
62 62
44 44
60 60
59 59

*/

Compilation message (stderr)

fever.cpp:2:1: warning: "/*" within comment [-Wcomment]
    2 | /**
      |

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31