제출 #66021

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

treasure

#include "treasure.h"
#include <bits/stdc++.h>
#define LSOne(S) (S & (-S))
using namespace std;
 
const int MAXN = 110;
 
static int matriz[MAXN][MAXN],bit[MAXN][MAXN],N;

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 x1,int y1,int x2,int y2){
  if(x1 > x2 || y1 > y2) return 0;
  return read(x2,y2) - read(x1-1,y2) - read(x2,y1-1) + read(x1-1,y1-1);
}

void solve(int x,int left,int right,int cnt){

	if(cnt == 0) return;
	if(right - left + 1 == cnt){
		for(int i = left;i<=right;i++){
			matriz[x][i] = 1;
      update(x,i,1);
		}
		return;
	}
 
	int mid = (left+right)/2;
 
	int qt = countTreasure(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){
 	
  N = n;
	memset(matriz,0,sizeof(matriz));
    int cnt = countTreasure(1, 1, N, N);
  	
  	int last = 0;
 
  	for(int i = 1;i<=N;i++){
  		int novo = countTreasure(1,1,i,N);
  		solve(i,1,N,novo - last);
  		last = novo;
  	}
 
  	for(int i = 1;i<=N;i++){
  		for(int j = 1;j<=N;j++){
  			if(matriz[i][j]) Report(i,j);
  		}
  	}
 
}

컴파일 시 표준 에러 (stderr) 메시지

treasure.cpp: In function 'void findTreasure(int)':
treasure.cpp:56:9: warning: unused variable 'cnt' [-Wunused-variable]
     int cnt = countTreasure(1, 1, N, N);
         ^~~

• Subtask 1: 72 / 100