제출 #65708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65708		IvanC	보물 찾기 (CEOI13_treasure2)	C++17	80 / 100	14 ms	1408 KiB

treasure

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

typedef tuple<int,int,int,int> quadra;

const int MAXN = 110;

static int matriz[MAXN][MAXN],N;
static map<quadra,int> previous_queries;

int doQuery(int x_i,int y_i,int x_f,int y_f){
	if(x_i > x_f || y_i > y_f || min(x_i,x_f) == 0 || min(y_i,y_f) == 0 || max(x_i,x_f) > N || max(y_i,y_f) > N) return 0;
	quadra davez = make_tuple(x_i,y_i,x_f,y_f);
	if(previous_queries.count(davez)) return previous_queries[davez];
	int qt = countTreasure(x_i, y_i, x_f, y_f);
	previous_queries[davez] = qt;
	return qt;
}

void findTreasure(int n){
 	
 	previous_queries.clear();
	memset(matriz,-1,sizeof(matriz));
  	N = n;

  	int mid = (1 + N)/2;
  
  	// Quarto inferior direito
  	for(int i = mid;i<=N;i++){
  		for(int j = mid;j<=N;j++){
  			if(matriz[i][j] != -1) continue;
  			matriz[i][j] = doQuery(1,1,i,j) - doQuery(1,1,i-1,j) - doQuery(1,1,i,j-1) + doQuery(1,1,i-1,j-1);
  		}
  	}

  	// Quarto inferior esquerdo
  	for(int i = mid;i<=N;i++){
  		for(int j = mid;j>=1;j--){
  			if(matriz[i][j] != -1) continue;
  			matriz[i][j] = doQuery(1,j,i,N) - doQuery(1,j,i-1,N) - doQuery(1,j+1,i,N) + doQuery(1,j+1,i-1,N);
  		}
  	}

  	// Quarto superior esquerdo
  	for(int i = mid;i>=1;i--){
  		for(int j = mid;j>=1;j--){
  			if(matriz[i][j] != -1) continue;
  			matriz[i][j] = doQuery(i,j,N,N) - doQuery(i+1,j,N,N) - doQuery(i,j+1,N,N) + doQuery(i+1,j+1,N,N);
  		}
  	}

  	// Quarto superior direito
  	for(int i = mid;i>=1;i--){
  		for(int j = mid;j<=N;j++){
  			if(matriz[i][j] != -1) continue;
  			matriz[i][j] = doQuery(i,1,N,j) - doQuery(i+1,1,N,j) - doQuery(i,1,N,j-1) + doQuery(i+1,1,N,j-1);
  		}
  	}

  	for(int i = 1;i<=N;i++){
  		for(int j = 1;j<=N;j++){
  			if(matriz[i][j] == 1) Report(i,j);
  		}
  	}

}

• Subtask 1: 80 / 100