#include "treasure.h"
#include <iostream>
using namespace std;
// bool arr[101][101];
// 체크대신에 그냥 바로 Report하면되네
//1+N*N-S의 에너지 사용을 N^2 + 7/16*N^4 이하로 사용하게 하여라
void check_treasure(int s_x,int s_y,int e_x,int e_y){
for(int i=s_x;i<=e_x;i++)
for(int j=s_y;j<=e_y;j++){
// cout << "report : " << i << "," << j << endl;
Report(i,j);
}
}
int cnt_map(int s_x,int s_y,int e_x,int e_y){
return (e_x-s_x+1)*(e_y-s_y+1);
}
//1,1 / 1,2
//1,1 to 1,1
//1,1 to 1,2
void find_treasure(int s_x,int s_y,int e_x,int e_y){
//기저는 len == 1일때 끝
//너무 작은거같긴하다 1,2여도 끝내도되지않을까 싶긴한데
if(s_x==e_x && s_y==e_y){
if(countTreasure(s_x,s_y,e_x,e_y)){
// cout << "count 1 : " << s_x << " , " << s_y << endl;
check_treasure(s_x,s_y,e_x,e_y);
}
return;
}
//1,1,N,N 에서 N*N개만큼 있으면 더 찾을 필요 X
//위를 찾을지 왼쪽를찾을지
//위에 없으면 아래인거지
//이런식으로 해야겠다.
//왼쪽에 없으면 오른쪽
//s_x,e_x가 같지만 않으면 좌우로 먼저 분할
//0이면 더 들어가지 않는것을 추가
// cout << "pos : " << s_x << " " << s_y << " to " << e_x << " " << e_y <<endl;
int cnt = countTreasure(s_x,s_y,e_x,e_y);//중복해서 세는느낌이라 parameter로 전달해야할듯
//11 to 12
if(cnt){
if(s_x!=e_x){
int mid = (s_x+e_x)/2;
int a = countTreasure(s_x,s_y,mid,e_y);
int b = cnt-a;//반대편은 cnt-a로 정의 가능
// cout << "cnt : " << cnt << " and a : " << a << " and b: " << b << endl;
if(a==cnt_map(s_x,s_y,mid,e_y)){
check_treasure(s_x,s_y,mid,e_y);
// cout << "check : " << s_x << " " << s_y << " to " << mid << " " << e_y <<endl;
}else if(a>0){//0이면 할필요가없음{
// cout << "traverse x A: " << s_x << " " << s_y << " to " << mid << " " << e_y <<endl;
find_treasure(s_x,s_y,mid,e_y);
}
if(b==cnt_map(mid+1,s_y,e_x,e_y)){
check_treasure(mid+1,s_y,e_x,e_y);
// cout << "check : " << mid+1 << " " << s_y << " to " << e_x << " " << e_y <<endl;
}else if(b>0)
find_treasure(mid+1,s_y,e_x,e_y);
}else if(s_y!=e_y){
int mid = (s_y+e_y)/2;
int a = countTreasure(s_x,s_y,e_x,mid);//얘가 0이면
int b = cnt-a;
// cout << "cnt : " << cnt << " and a : " << a << " and b: " << b << endl;
if(a==cnt_map(s_x,s_y,e_x,mid))
check_treasure(s_x,s_y,e_x,mid);
else if(a>0){
// cout << "traverse y A: " << s_x << " " << s_y << " to " << mid << " " << e_y <<endl;
find_treasure(s_x,s_y,e_x,mid);
}
if(b==cnt_map(s_x,mid+1,e_x,e_y))
check_treasure(s_x,mid+1,e_x,e_y);
else if(b>0){
// cout << "traverse y B: " << s_x << " " << s_y << " to " << mid << " " << e_y <<endl;
find_treasure(s_x,mid+1,e_x,e_y);
}
}
}
}
void findTreasure (int N) {
// int cnt = countTreasure(1, 1, N, N);
find_treasure(1,1,N,N);
// cout << "end" << endl;
//얘가 1
//분할정복으로 하면 안되나?
// cout << arr[1][1] << endl;
// if(cnt > 0){
// Report (1, 2);
// Report (2,2);
// Report (2,1);
// }
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Error - you cannot call countTreasure() after calling Report() |
| 2 |
Incorrect |
1 ms |
384 KB |
Error - you cannot call countTreasure() after calling Report() |
| 3 |
Incorrect |
1 ms |
364 KB |
Error - you cannot call countTreasure() after calling Report() |
| 4 |
Incorrect |
0 ms |
236 KB |
Error - you cannot call countTreasure() after calling Report() |
| 5 |
Incorrect |
1 ms |
364 KB |
Error - you cannot call countTreasure() after calling Report() |
| 6 |
Incorrect |
1 ms |
364 KB |
Error - you cannot call countTreasure() after calling Report() |
| 7 |
Incorrect |
1 ms |
384 KB |
Error - you cannot call countTreasure() after calling Report() |
| 8 |
Incorrect |
1 ms |
364 KB |
Error - you cannot call countTreasure() after calling Report() |
| 9 |
Incorrect |
1 ms |
364 KB |
Error - you cannot call countTreasure() after calling Report() |
| 10 |
Incorrect |
1 ms |
384 KB |
Error - you cannot call countTreasure() after calling Report() |
