제출 #852729

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
852729		danikoynov	IOI 바이러스 (JOI21_fever)	C++14	37 / 100	708 ms	41048 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;
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 cmp(collision c1, collision c2)
{
    return c1.tp < c2.tp;
}
int simulate()
{


    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;
            }
        }
    }
    /**cout << "simulate " << endl;
    for (int i = 1; i <= n; i ++)
        cout << p[i].x << " " << p[i].y << " " << dir[i] << endl;*/
    vector < collision > event;
    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

*/

컴파일 시 표준 에러 (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: 0 / 32
• Subtask 7: 0 / 31