제출 #221456

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
221456		glikcakbn	여왕벌 (KOI15_queen)	C++14	101 / 100	2041 ms	97280 KiB

Main

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 24 / 24
• Subtask 3: 34 / 34
• Subtask 4: 32 / 32
• Subtask 5: 1 / 1