답안 #362257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
362257	2021-02-02T11:34:45 Z	cheongm	보물 찾기 (CEOI13_treasure2)	C++14	59 / 100	1 ms	492 KB

treasure

#include "treasure.h"
#include<cstdio>
#include<vector>

using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;
/*
   ab
   cd
   ab, bd, dc,ac로 접근
 */

void findTreasure(int r1, int c1, int r2, int c2, int remain,vii& v)
{
  	/*
    int k;
    scanf("%d",&k);
    printf("{{%d,%d},{%d,%d},%d}\n",r1,c1,r2,c2,remain);
    */
    if(r1>r2||c1>c2)
        return ;

    if(remain ==(r2-r1+1)*(c2-c1+1))//사각형안에 1꽉차있으면
    {
        for(int i=r1;i<=r2;i++)
            for(int j=c1;j<=c2;j++)
                v.push_back(make_pair(i,j));

    }
    else if(remain>0)//사각형안에 1이 있긴하면
    {
        if(r1==r2)//무한루프때문에
        {
            int cmid = (c1+c2)/2;
            int a = countTreasure(r1,c1,r1,cmid);
            if(a==remain)
                findTreasure(r1,c1,r1,cmid,remain,v);
            else if(a==0)
                findTreasure(r1,cmid+1,r1,c2,remain,v);
            else
            {
                findTreasure(r1,c1,r1,cmid,a,v);
                findTreasure(r1,cmid+1,r1,c2,remain-a,v);
            }
        }
        else if(c1==c2)
        {
            int rmid = (r1+r2)/2;
            int a = countTreasure(r1,c1,rmid,c1);
            if(a==remain)
                findTreasure(r1,c1,rmid,c1,remain,v);
            else if(a==0)
                findTreasure(rmid+1,c1,r2,c1,remain,v);
            else
            {
                findTreasure(r1,c1,rmid,c1,a,v);
                findTreasure(rmid+1,c1,r2,c1,remain-a,v);
            }
        }
        else
        {
            int rmid = (r1+r2)/2;
            int cmid = (c1+c2)/2;
            int ab;


            ab = countTreasure(r1,c1,rmid,c2);
            if(ab == remain)
                findTreasure(r1,c1,rmid,c2,remain,v);
            else if(ab==0)//cd == remain
                findTreasure(rmid+1,c1,r2,c2,remain,v);
            else
            {
                int ac = countTreasure(r1,c1,r2,cmid);
                if(ac == remain)
                    findTreasure(r1,c1,r2,cmid,remain,v);
                else if(ac==0)//bd == remain
                    findTreasure(r1,cmid+1,r2,c2,remain,v);
                else//d를알아야함
                {
                    /*
                       int d = countTreasure(rmid+1,cmid+1,r2,c2);<<홀수일떄 더작기때문에 바꿈
                       int c = remain-ab-d;
                       int b = remain-ac-d;
                       int a = ac-c;
                     */
                    int a = countTreasure(r1,c1,rmid,cmid);
                    int b = ab-a;
                    int c = ac-a;
                    int d = remain-a-b-c;
                    findTreasure(r1,c1,rmid,cmid,a,v);
                    findTreasure(r1,cmid+1,rmid,c2,b,v);
                    findTreasure(rmid+1,c1,r2,cmid,c,v);
                    findTreasure(rmid+1,cmid+1,r2,c2,d,v);
                }
            }
        }
    }
}
void findTreasure (int N) {
    vii v;
    int cnt = countTreasure(1,1,N,N);
    if(cnt)
        findTreasure(1,1,N,N,cnt,v);
    for(vii::iterator iter = v.begin(); iter!=v.end(); iter++)
        Report(iter->first,iter->second);
}

Subtask #1

59.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	1 ms	384 KB	Output is partially correct - N = 5, K = 436, score = 8
2	Partially correct	0 ms	376 KB	Output is partially correct - N = 10, K = 6740, score = 4
3	Correct	1 ms	384 KB	Output is correct - N = 15, K = 12314, score = 10
4	Correct	1 ms	384 KB	Output is correct - N = 16, K = 15572, score = 10
5	Partially correct	1 ms	364 KB	Output is partially correct - N = 55, K = 6737755, score = 4
6	Partially correct	1 ms	364 KB	Output is partially correct - N = 66, K = 14533122, score = 1
7	Correct	1 ms	384 KB	Output is correct - N = 77, K = 4386571, score = 10
8	Correct	1 ms	492 KB	Output is correct - N = 88, K = 5365930, score = 10
9	Partially correct	1 ms	492 KB	Output is partially correct - N = 99, K = 72480069, score = 1
10	Partially correct	1 ms	492 KB	Output is partially correct - N = 100, K = 76451562, score = 1