Submission #362257

#	Time	Username	Problem	Language	Result	Execution time	Memory
362257		cheongm	Treasure (different grader from official contest) (CEOI13_treasure2)	C++14	59 / 100	1 ms	492 KiB

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 / 100