제출 #111883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
111883		RezwanArefin01	보물 찾기 (CEOI13_treasure2)	C++17	73 / 100	23 ms	1152 KiB

treasure

#include <bits/stdc++.h>
#include "treasure.h"
using namespace std; 

typedef pair<int, int> ii; 

map<pair<ii, ii>, int> mp; 
int grid[101][101], vis[101][101], n;

int ask(int x1, int y1, int x2, int y2) {
    if(x1 > x2 || y1 > y2) return 0; 
    pair<ii, ii> key = {{x1, y1}, {x2, y2}}; 
    if(!mp.count(key)) mp[key] = countTreasure(x1, y1, x2, y2); 
    return mp[key]; 
}

int get(int x1, int y1, int x2, int y2) {
    if(x1 > x2 || y1 > y2) return 0; 
    pair<ii, ii> key = {{x1, y1}, {x2, y2}}; 
    if(mp.count(key)) return 0; 
    return 1 + n * n - (x2 - x1 + 1) * (y2 - y1 + 1); 
}

int solve(int i, int j) {
    int op11 = get(1, 1, i, j) + get(1, 1, i - 1, j) + get(1, 1, i, j - 1) + get(1, 1, i - 1, j - 1); 
    int opnn = get(i, j, n, n) + get(i, j + 1, n, n) + get(i + 1, j, n, n) + get(i + 1, j + 1, n, n); 
    int op1n = get(1, j, i, n) + get(1, j, i - 1, n) + get(1, j + 1, i, n) + get(1, j + 1, i - 1, n);
    int opn1 = get(i, 1, n, j) + get(i, 1, n, j - 1) + get(i + 1, 1, n, j) + get(i + 1, 1, n, j - 1);

    int mn = min({op11, opnn, op1n, opn1});
    if(op11 == mn) {
        return ask(1, 1, i, j) - ask(1, 1, i - 1, j) - ask(1, 1, i, j - 1) + ask(1, 1, i - 1, j - 1); 
    } else if(opnn == mn) {
        return ask(i, j, n, n) - ask(i, j + 1, n, n) - ask(i + 1, j, n, n) + ask(i + 1, j + 1, n, n); 
    } else if(op1n == mn) {
        return ask(1, j, i, n) - ask(1, j, i - 1, n) - ask(1, j + 1, i, n) + ask(1, j + 1, i - 1, n);
    } else {
        return ask(i, 1, n, j) - ask(i, 1, n, j - 1) - ask(i + 1, 1, n, j) + ask(i + 1, 1, n, j - 1);
    }
}
void findTreasure (int N) { n = N;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(n & 1) {
                if(i == (n + 1) / 2 || j == (n + 1) / 2) continue; 
            } else {
                if(i == n / 2 || i == n / 2 + 1 || j == n / 2 || j == n / 2 + 1) continue; 
            }
            vis[i][j] = 1; 
            grid[i][j] = solve(i, j); 
        }
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(!vis[i][j]) grid[i][j] = solve(i, j); 
        }
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(grid[i][j]) Report(i, j);
        }
    }
}

• Subtask 1: 73 / 100