제출 #55443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55443		gs18081	보물 찾기 (CEOI13_treasure2)	C++11	10 / 100	2 ms	824 KiB

treasure

#include "treasure.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pi;
vector<pi> ans;
int find(int y1,int x1,int y2,int x2){
    int cnt=countTreasure(y1,x1,y2,x2);
    if(x1==x2){
        if(cnt==1){
            ans.push_back(pi(y1,x1));
        }
        return cnt;
    }
    int size=(x2-x1+1)*(x2-x1+1);
    int remain=cnt;
    int y3=(y1+y2)>>1;
    int x3=(x1+x2)>>1;
    int pos[4][4]={{y1,x1,y3,x3},{y1,x3+1,y3,x2},{y3+1,x1,y2,x3},{y3+1,x3+1,y2,x2}};
    for(int i=0;i<4;i++){
        int *now=pos[i];
        if(remain==size){
            for(int j=now[0];j<=now[2];j++){
                for(int k=now[1];k<=now[3];k++){
                    ans.push_back(pi(j,k));
                }
            }
            remain-=(now[2]-now[0]+1)*(now[3]-now[1]+1);
        }
        else if(remain==0) break;
        else{
            remain-=find(now[0],now[1],now[2],now[3]);
        }
        size-=(now[2]-now[0]+1)*(now[3]-now[1]+1);
    }
    return cnt;
}
void findTreasure (int N) {
    find(1,1,N,N);
    for(auto i:ans){
        Report(i.first,i.second);
    }
}

• Subtask 1: 10 / 100