제출 #111880

#제출 시각아이디문제언어결과실행 시간메모리
111880RezwanArefin01보물 찾기 (CEOI13_treasure2)C++17
44 / 100
17 ms1024 KiB
#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], 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); } void findTreasure (int N) { n = N; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++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) { grid[i][j] = 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) { grid[i][j] = 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) { grid[i][j] = 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 { grid[i][j] = ask(i, 1, n, j) - ask(i, 1, n, j - 1) - ask(i + 1, 1, n, j) + ask(i + 1, 1, n, j - 1); } } } for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { if(grid[i][j]) Report(i, j); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...