Submission #111880

#	Time	Username	Problem	Language	Result	Execution time	Memory
111880		RezwanArefin01	Treasure (different grader from official contest) (CEOI13_treasure2)	C++17	44 / 100	17 ms	1024 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], 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);
        }
    }
}

• Subtask 1: 44 / 100