제출 #270606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
270606		johutha	보물 찾기 (CEOI13_treasure2)	C++17	0 / 100	1 ms	512 KiB

treasure

#include <iostream>
#include <vector>
#include <memory>
#include "treasure.h"

#define int int64_t

using namespace std;

int n;

pair<int,int> rotate(pair<int,int> p, int rot)
{
    if (rot == 1) return make_pair(p.second, n - 1 - p.first);
    if (rot == 2) return make_pair(n - 1 - p.first, n - 1 - p.second);
    if (rot == 3) return make_pair(n - 1 - p.second, p.first);
    return p;
}

int query(int y1, int x1, int y2, int x2, int rot)
{
    tie(y1, x1) = rotate(make_pair(y1, x1), rot);
    tie(y2, x2) = rotate(make_pair(y2, x2), rot);
    return countTreasure(min(y1, y2) + 1, min(x1, x2) + 1, max(y1, y2) + 1, max(x1, x2) + 1);
}

void findTreasure (signed N)
{
    n = N;

    vector<int> ar = {n / 2, n - (n / 2)};

    vector<vector<int>> res(n, vector<int>(n, -1));

    for (int rt = 0; rt < 4; rt++)
    {
        int r = ar[rt / 2];
        int c = ar[(rt / 2 == 1) ^ (rt % 2 == 0)];
        
        vector<vector<int>> qr(r + 1, vector<int>(c + 1, -1));

        for (int i = 0; i <= r; i++)
        {
            for (int j = 0; j <= c; j++)
            {
                int y = n - r - 1 + i;
                int x = n - c - 1 + j;
                qr[i][j] = query(y, x, 0, 0, rt);
            }
        }

        for (int i = 0; i < r; i++)
        {
            for (int j = 0; j < c; j++)
            {
                int y = n - r + i;
                int x = n - c + j;
                tie(y, x) = rotate(make_pair(y, x), rt);
                res[y][x] = qr[i][j] + qr[i + 1][j + 1] - qr[i + 1][j] - qr[i][j + 1];
            }
        }
    }
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (res[i][j] == 1) Report(i, j);
        }
    }
}

• Subtask 1: 0 / 100