제출 #66037

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

treasure

#include "treasure.h"
#include <bits/stdc++.h>
#define LSOne(S) (S & (-S))
using namespace std;

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

const int MAXN = 110;

static int matriz[MAXN][MAXN],N,bit[MAXN][MAXN];
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;
}

static void update(int x,int y,int delta){
  for(int i = x;i<=N;i += LSOne(i)){
    for(int j = y;j<=N;j += LSOne(j)){
      bit[i][j] += delta;
    }
  }
}

static int read(int x,int y){
  int ans = 0;
  for(int i = x;i>0;i -= LSOne(i)){
    for(int j = y;j > 0;j -= LSOne(j)){
      ans += bit[i][j];
    }
  }
  return ans;
}

static int query2d(int x_i,int y_i,int x_f,int y_f){
  if(x_i > x_f || y_i > y_f) return 0;
  return read(x_f,y_f) - read(x_i-1,y_f) - read(x_f,y_i-1) + read(x_i-1,y_i-1);
}

void solve(int x,int left,int right,int cnt){
 
  if(cnt == 0){
    for(int i = left;i<=right;i++){
      matriz[x][i] = 0;
    }
    return;
  }
  if(right - left + 1 == cnt){
    for(int i = left;i<=right;i++){
      if(matriz[x][i] != -1) continue;
      matriz[x][i] = 1;
      update(x,i,1);
    }
    return;
  }
 
  int mid = (left+right)/2;
 
  int qt = doQuery(1,1,x,mid) - query2d(1,1,x,left - 1) - query2d(1,left,x-1,mid);
  solve(x,left,mid,qt);
  solve(x,mid+1,right,cnt - qt);
 
}

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

    int mid = (1 + N)/2;
  
    // Quarto inferior esquerdo
    for(int i = mid;i<=N;i++){
      for(int j = mid-1;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-1;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-1;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);
      }
    }

    // Constroi BIT 2d
    for(int i = 1;i<=N;i++){
      for(int j = 1;j<=N;j++){
        if(matriz[i][j] != -1){
          update(i,j,matriz[i][j]);
        }
      }
    }

    // Quarto inferior direito
    for(int i = mid;i<=N;i++){
      int qt = doQuery(1,1,i,N) - query2d(1,1,i,mid-1) - query2d(1,mid,i-1,N);
      solve(i,mid,N,qt);
    }


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

}

• Subtask 1: 96 / 100