Submission #362211

#	Time	Username	Problem	Language	Result	Execution time	Memory
362211		ray5273	Treasure (different grader from official contest) (CEOI13_treasure2)	C++14	0 / 100	1 ms	384 KiB

treasure

#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);
    // }
}

• Subtask 1: 0 / 100