Submission #66021

#	Time	Username	Problem	Language	Result	Execution time	Memory
66021		IvanC	Treasure (different grader from official contest) (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);
  		}
  	}
 
}

Compilation message (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