oj.uz

Submission #347481

# Submission time Handle Problem Language Result Execution time Memory
347481 2021-01-13T06:19:37 Z blue Park (BOI16_park) C++11
0 / 100
 2500 ms 15980 KB 
#include <iostream>
#include <vector>
using namespace std;

int sq(int a)
{
    return a*a;
}

int sq_rt(int a, int l, int u)
{
    if(l == u) return l;
    int m = (l+u)/2+1;

    if(m*m > a) return sq_rt(a, l, m-1);
    else return sq_rt(a, m, u);
}

int main()
{
    int n, m;
    cin >> n >> m;


    int w, h;
    cin >> w >> h;

    int x[n], y[n], r[n];
    for(int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i] >> r[i];
    }

    //n = bottom edge, n+1 = right edge, n+2 = top edge, n+3 = left edge

    int maxGap[n+4][n+4];

    for(int i = 0; i < n; i++)
    {
        maxGap[i][n] = maxGap[n][i] = y[i] - r[i];
        maxGap[i][n+1] = maxGap[n+1][i] = w - (x[i] + r[i]);
        maxGap[i][n+2] = maxGap[n+2][i] = h - (y[i] + r[i]);
        maxGap[i][n+3] = maxGap[n+3][i] = x[i] - r[i];
    }

    for(int i = n; i < n+4; i++)
        for(int j = i+1; j < n+4; j++)
            maxGap[i][j] = maxGap[j][i] = 1e9;

    for(int i = 0; i < n; i++)
    {
        for(int j = i+1; j < n; j++)
        {
            maxGap[i][j] = maxGap[j][i] = sq_rt(sq(x[i] - x[j]) + sq(y[i] - y[j]), 0, 10000) - r[i] - r[j];
        }
    }







    for(int k = 0; k < n+4; k++)
    {
        for(int i = 0; i < n+4; i++)
        {
            if(i == k) continue;
            for(int j = 0; j < n+4; j++)
            {
                if(j == i || j == k) continue;

                maxGap[i][j] = min(maxGap[i][j], max(maxGap[i][k], maxGap[k][j]) );
            }
        }
    }


    // for(int i = 0; i < n+4; i++)
    // {
    //     for(int j = 0; j < n+4; j++)
    //     {
    //         if(i == j) cout << "* ";
    //         else cout << maxGap[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }

    int cornerGap[5][5];
    for(int i = 0; i < 5; i++) for(int j = 0; j < 5; j++) cornerGap[i][j] = 1e9;

    vector<int> A, B;
    for(int i = 1; i <= 4; i++)
    {
        for(int j = i; j <= 4; j++)
        {
            cornerGap[i][j] = cornerGap[j][i] = 1e9;
            A.clear();
            B.clear();

            for(int k = 0; k < 4; k++)
            {
                if(i-1 <= k && k < j-1) A.push_back(n+k);
                else B.push_back(n+k);
            }

            for(int a:A) for(int b:B)
                cornerGap[i][j] = cornerGap[j][i] = min(cornerGap[i][j], maxGap[a][b]);
        }
    }

    // for(int i = 1; i <= 4; i++)
    // {
    //     for(int j = 1; j <= 4; j++) cout << cornerGap[i][j] << ' ';
    //     cout << '\n';
    // }



    int R, E;
    for(int i = 0; i < m; i++)
    {
        cin >> R >> E;
        for(int j = 1; j <= 4; j++)
        {
            if(cornerGap[E][j] >= 2*R) cout << j;
        }
        cout << '\n';
    }
}

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2568 ms 15980 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 310 ms 748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2568 ms 15980 KB Time limit exceeded
2 Halted 0 ms 0 KB -