Submission #852776

#	Time	Username	Problem	Language	Result	Execution time	Memory
852776		danikoynov	IOI Fever (JOI21_fever)	C++14	100 / 100	4700 ms	72888 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 = 1e5 + 10;
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];
unordered_map < int, set < pair < int, int > > > mrow[4], fcol[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;
    int dist = (used[id] + 1) / 2;
    if (dir[id] == 0)
    {
        it = mdig[3][md].lower_bound({p[id].x + dist, -inf});
        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 - dist, inf});
        if (it != fdig[1][fd].begin())
        {
            it = prev(it);
            collision cur(id, it -> second, get_collision_time(id, it -> second));
            nxt = min(nxt, cur);
        }

        it = fcol[2][p[id].x].lower_bound({p[id].y + used[id], -inf});
        if (it != fcol[2][p[id].x].end())
        {
            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 + dist, - inf});
        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 + dist, -inf});
        if (it != fdig[0][fd].end())
        {
            collision cur(id, it -> second, get_collision_time(id, it -> second));
            nxt = min(nxt, cur);
        }

        it = mrow[3][p[id].y].lower_bound({p[id].x + used[id], -inf});
        if (it != mrow[3][p[id].y].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 - dist, inf});
        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 + dist, -inf});
        if (it != fdig[3][fd].end())
        {
            collision cur(id, it -> second, get_collision_time(id, it -> second));
            nxt = min(nxt, cur);
        }

        it = fcol[0][p[id].x].lower_bound({p[id].y - used[id], inf});
        if (it != fcol[0][p[id].x].begin())
        {
            it = prev(it);
            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 - dist, inf});
        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 - dist, inf});
        if (it != fdig[2][fd].begin())
        {
            it = prev(it);
            collision cur(id, it -> second, get_collision_time(id, it -> second));
            nxt = min(nxt, cur);
        }

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

        }
    }


    ///cout << "next collision " << id << " " << nxt.idx2 << " " << nxt.tp << endl;
    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});
    mrow[dir[i]][p[i].y].insert({p[i].x, i});
    fcol[dir[i]][p[i].x].insert({p[i].y, 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});
    mrow[dir[i]][p[i].y].erase({p[i].x, i});
    fcol[dir[i]][p[i].x].erase({p[i].y, i});
}
int simulate()
{
    for (int i = 0; i < 4; i ++)
    {
        mdig[i].clear();
        fdig[i].clear();
        mrow[i].clear();
        fcol[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] = -1;
    }
    used[1] = 0;
    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)
        {
            get_next_collsion(cur.idx1);
            continue;
        }
        ///cout << "collision " << cur.idx1 << " " << cur.idx2 << " " << cur.tp << endl;
        used[cur.idx2] = cur.tp;
        ans ++;

        rem_point(cur.idx2);
        get_next_collsion(cur.idx1);
        get_next_collsion(cur.idx2);
    }

    ///cout << ans << endl;
    ///exit(0);
    return ans;
}

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;
    /**perform90();
    perform90();
    perform90();
    simulate();*/
    for (int d = 0; d < 4; d ++)
    {
        ans = max(ans, simulate());
        perform90();
    }

    cout << ans << endl;

}

int main()
{
    speed();
    solve();
    return 0;
}
/**

15
107 139
114 146
105 137
88 120
130 130
112 148
123 123
93 93
128 128
113 113
106 140
99 147
146 100
108 142
115 135

7
64 52
68 56
65 53
62 62
44 44
60 60
59 59


3
0 0
1 1
-1 3

15
0 0
7 7
-2 -2
-19 -19
23 -9
5 9
16 -16
-14 -46
21 -11
6 -26
-1 1
-8 8
39 -39
1 3
8 -4


collision 1 3 4
collision 2 3 18
collision 1 7 32
collision 2 5 32
collision 11 7 34
collision 5 10 34
collision 6 5 36
collision 1 4 38
collision 12 7 48
collision 7 8 60
collision 9 8 70
collision 1 13 78
*/

Compilation message (stderr)

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

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