oj.uz

Submission #221456

# Submission time Handle Problem Language Result Execution time Memory
221456 2020-04-10T07:53:57 Z glikcakbn 여왕벌 (KOI15_queen) C++14
101 / 100
 2041 ms 97280 KB 
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss

using namespace std;

string S[705][705];
int ans[705][705];

vector<vector<pii>> f(int lx, int rx, int ly, int ry, vector<vector<int>> cnt)
{
    int m = rx - lx + ry - ly + 1;
    vector<vector<pii>> ret(m + 1);
    for(int i = 0; i <= m; ++i) ret[i].resize(i + 1);

    if(lx == rx || ly == ry)
        for(int i = 0; i <= m; ++i) for(int j = 0; j <= i; ++j) ret[i][j] = {i, j};

    else if(m == 3)
    {
        for(int i = 0; i <= 3; ++i)
        {
            for(int j = 0; j <= i; ++j)
            {
                int arr[3];
                if(j >= 1) arr[0] = 0; else if(i >= 1) arr[0] = 1; else arr[0] = 2;
                if(j >= 2) arr[1] = 0; else if(i >= 2) arr[1] = 1; else arr[1] = 2;
                if(j >= 3) arr[2] = 0; else if(i >= 3) arr[2] = 1; else arr[2] = 2;
                char c = S[ly][lx][arr[0] * 9 + arr[1] * 3 + arr[2]];
                if(c == 'L') arr[1] = arr[0];
                if(c == 'U') arr[1] = arr[2];
                pii tmp = {0, 0};
                if(arr[0] == 0) ++tmp.ff, ++tmp.ss; else if(arr[0] == 1) ++tmp.ff;
                if(arr[1] == 0) ++tmp.ff, ++tmp.ss; else if(arr[1] == 1) ++tmp.ff;
                if(arr[2] == 0) ++tmp.ff, ++tmp.ss; else if(arr[2] == 1) ++tmp.ff;
                ans[ly][lx] += arr[1] * cnt[i][j];
                ret[i][j] = tmp;
            }
        }
    }

    else
    {
        int mx = lx + rx >> 1, my = ly + ry >> 1;
        int A = mx - lx, B = rx - mx, C = my - ly, D = ry - my;
        vector<vector<pii>> conv(m + 1);
        for(int i = 0; i <= m; ++i) conv[i].resize(i + 1);
        for(int i = 0; i <= m; ++i) for(int j = 0; j <= i; ++j) conv[i][j] = {i, j};

        int m1 = A + C + 1;
        vector<vector<int>> c1(m1 + 1);
        for(int i = 0; i <= m1; ++i) c1[i].resize(i + 1);
        for(int i = 0; i <= m; ++i)
            for(int j = 0; j <= i; ++j)
                c1[max(0, min(i, m - B) - D)][max(0, min(j, m - B) - D)] += cnt[i][j];
        auto q1 = f(lx, mx, ly, my, c1);
        for(int i = 0; i <= m; ++i)
        {
            for(int j = 0; j <= i; ++j)
            {
                int x = conv[i][j].ff, y = conv[i][j].ss, _x, _y;
                if(x < D || x > m - B) _x = x;
                else _x = D + q1[max(0, min(x, m - B) - D)][max(0, min(y, m - B) - D)].ff;
                if(y < D || y > m - B) _y = y;
                else _y = D + q1[max(0, min(x, m - B) - D)][max(0, min(y, m - B) - D)].ss;
                conv[i][j] = {_x, _y};
            }
        }
        vector<vector<int>>().swap(c1);
        vector<vector<pii>>().swap(q1);

        int m2 = B + C + 1;
        vector<vector<int>> c2(m2 + 1);
        for(int i = 0; i <= m2; ++i) c2[i].resize(i + 1);
        for(int i = 0; i <= m; ++i)
        {
            for(int j = 0; j <= i; ++j)
            {
                int x = conv[i][j].ff, y = conv[i][j].ss;
                c2[max(0, x - A - D)][max(0, y - A - D)] += cnt[i][j];
            }
        }
        auto q2 = f(mx, rx, ly, my, c2);
        for(int i = 0; i <= m; ++i)
        {
            for(int j = 0; j <= i; ++j)
            {
                int x = conv[i][j].ff, y = conv[i][j].ss, _x, _y;
                if(x < A + D) _x = x;
                else _x = A + D + q2[max(0, x - A - D)][max(0, y - A - D)].ff;
                if(y < A + D) _y = y;
                else _y = A + D + q2[max(0, x - A - D)][max(0, y - A - D)].ss;
                conv[i][j] = {_x, _y};
            }
        }
        vector<vector<int>>().swap(c2);
        vector<vector<pii>>().swap(q2);

        int m3 = A + D + 1;
        vector<vector<int>> c3(m3 + 1);
        for(int i = 0; i <= m3; ++i) c3[i].resize(i + 1);
        for(int i = 0; i <= m; ++i)
        {
            for(int j = 0; j <= i; ++j)
            {
                int x = conv[i][j].ff, y = conv[i][j].ss;
                c3[min(x, m - B - C)][min(y, m - B - C)] += cnt[i][j];
            }
        }
        auto q3 = f(lx, mx, my, ry, c3);
        for(int i = 0; i <= m; ++i)
        {
            for(int j = 0; j <= i; ++j)
            {
                int x = conv[i][j].ff, y = conv[i][j].ss, _x, _y;
                if(x > m - B - C) _x = x;
                else _x = q3[min(x, m - B - C)][min(y, m - B - C)].ff;
                if(y > m - B - C) _y = y;
                else _y = q3[min(x, m - B - C)][min(y, m - B - C)].ss;
                conv[i][j] = {_x, _y};
            }
        }
        vector<vector<int>>().swap(c3);
        vector<vector<pii>>().swap(q3);

        int m4 = B + D + 1;
        vector<vector<int>> c4(m4 + 1);
        for(int i = 0; i <= m4; ++i) c4[i].resize(i + 1);
        for(int i = 0; i <= m; ++i)
        {
            for(int j = 0; j <= i; ++j)
            {
                int x = conv[i][j].ff, y = conv[i][j].ss;
                c4[max(0, min(x, m - C) - A)][max(0, min(y, m - C) - A)] += cnt[i][j];
            }
        }
        auto q4 = f(mx, rx, my, ry, c4);
        for(int i = 0; i <= m; ++i)
        {
            for(int j = 0; j <= i; ++j)
            {
                int x = conv[i][j].ff, y = conv[i][j].ss, _x, _y;
                if(x < A || x > m - C) _x = x;
                else _x = A + q4[max(0, min(x, m - C) - A)][max(0, min(y, m - C) - A)].ff;
                if(y < A || y > m - C) _y = y;
                else _y = A + q4[max(0, min(x, m - C) - A)][max(0, min(y, m - C) - A)].ss;
                conv[i][j] = {_x, _y};
            }
        }
//        cout << lx << ' ' << rx << ' ' << ly << ' ' << ry << endl;
//        for(auto i : cnt) { for(auto j : i) cout << j << ' '; cout << endl; }
        vector<vector<int>>().swap(c4);
        vector<vector<pii>>().swap(q4);

        ret = conv;
    }

    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n; cin >> m >> n;
    for(int i = 1; i < m; ++i) for(int j = 1; j < m; ++j) cin >> S[i][j];

    vector<vector<int>> cnt(2 * m);
    for(int i = 0; i < 2 * m; ++i) cnt[i].resize(i + 1);
    int tmp[2 * m]{};
    for(int i = 0; i < n; ++i)
    {
        int x, y, z; cin >> x >> y >> z;
        ++cnt[x + y][x];
        ++tmp[x]; ++tmp[x + y];
    }
    for(int i = 1; i < 2 * m; ++i) tmp[i] += tmp[i - 1];
    for(int i = 0; i < m; ++i) ans[m - i - 1][0] = tmp[i];
    for(int i = 1; i < m; ++i) ans[0][i] = tmp[i + m - 1];
    f(1, m, 1, m, cnt);

    for(int i = 0; i < m; ++i)
    {
        for(int j = 0; j < m; ++j)
            cout << ans[i][j] + 1 << ' ';
        cout << '\n';
    }

    return 0;
}

Compilation message

queen.cpp: In function 'std::vector<std::vector<std::pair<int, int> > > f(int, int, int, int, std::vector<std::vector<int> >)':
queen.cpp:53:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mx = lx + rx >> 1, my = ly + ry >> 1;
                  ~~~^~~~
queen.cpp:53:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mx = lx + rx >> 1, my = ly + ry >> 1;
                                     ~~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16000 KB Output is correct
2 Correct 14 ms 16000 KB Output is correct
3 Correct 44 ms 17664 KB Output is correct
4 Correct 44 ms 17664 KB Output is correct
5 Correct 303 ms 29300 KB Output is correct
6 Correct 315 ms 29416 KB Output is correct
7 Correct 306 ms 29324 KB Output is correct
8 Correct 752 ms 51908 KB Output is correct
9 Correct 728 ms 52252 KB Output is correct
10 Correct 1736 ms 85796 KB Output is correct
11 Correct 1765 ms 85708 KB Output is correct
12 Correct 1768 ms 85756 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16000 KB Output is correct
2 Correct 301 ms 29468 KB Output is correct
3 Correct 538 ms 39352 KB Output is correct
4 Correct 1763 ms 85592 KB Output is correct
5 Correct 1715 ms 85772 KB Output is correct
6 Correct 1754 ms 85668 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16000 KB Output is correct
2 Correct 46 ms 17592 KB Output is correct
3 Correct 757 ms 52204 KB Output is correct
4 Correct 1733 ms 85820 KB Output is correct
5 Correct 1751 ms 85784 KB Output is correct
6 Correct 1759 ms 85748 KB Output is correct
7 Correct 1735 ms 85832 KB Output is correct
8 Correct 1701 ms 85880 KB Output is correct
9 Correct 1720 ms 85668 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1049 ms 63312 KB Output is correct
2 Correct 966 ms 63028 KB Output is correct
3 Correct 1947 ms 97052 KB Output is correct
4 Correct 1997 ms 97220 KB Output is correct
5 Correct 1991 ms 97280 KB Output is correct
6 Correct 2012 ms 97092 KB Output is correct
7 Correct 2033 ms 97016 KB Output is correct
8 Correct 2015 ms 97072 KB Output is correct
9 Correct 1967 ms 97172 KB Output is correct
10 Correct 1956 ms 97212 KB Output is correct

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15872 KB Output is correct
2 Correct 13 ms 15872 KB Output is correct
3 Correct 14 ms 15872 KB Output is correct
4 Correct 14 ms 15872 KB Output is correct
5 Correct 214 ms 21728 KB Output is correct
6 Correct 203 ms 21752 KB Output is correct
7 Correct 204 ms 21752 KB Output is correct
8 Correct 210 ms 21752 KB Output is correct
9 Correct 1965 ms 96936 KB Output is correct
10 Correct 1967 ms 96996 KB Output is correct
11 Correct 1920 ms 97020 KB Output is correct
12 Correct 1996 ms 96844 KB Output is correct
13 Correct 2031 ms 96852 KB Output is correct
14 Correct 1992 ms 97248 KB Output is correct
15 Correct 2007 ms 97168 KB Output is correct
16 Correct 1936 ms 97144 KB Output is correct
17 Correct 2016 ms 97004 KB Output is correct
18 Correct 2041 ms 97060 KB Output is correct