oj.uz

Submission #361823

# Submission time Handle Problem Language Result Execution time Memory
361823 2021-01-31T17:10:44 Z cheongm Treasure (different grader from official contest) (CEOI13_treasure2) C++14
56 / 100
 1 ms 512 KB 
#include "treasure.h"
#include<cstdio>
#include<vector>

using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;

int findTreasure(int r1, int c1, int r2, int c2, int remain,vii& v)
{
    if(r1>r2||c1>c2)
        return 0;
    //printf("---- %d %d %d %d ----\n",r1,c1,r2,c2);
    int cnt,rval;
    if(remain)
        cnt = remain;
    else
        cnt = countTreasure(r1,c1,r2,c2);
    rval=cnt;

    if(cnt ==(r2-r1+1)*(c2-c1+1))
    {
        for(int i=r1;i<=r2;i++)
            for(int j=c1;j<=c2;j++)
            {
                //printf("{%d,%d}\n",i,j);
                v.push_back(make_pair(i,j));
            }
    }
    else if(cnt>0)
    {
        int rmid = (r1+r2)/2;
        int cmid = (c1+c2)/2;
        int is_full = false;
        cnt -=findTreasure(r1,c1,rmid,cmid,0,v);
        if((r2-rmid)*(c2-c1+1)+(rmid-r1+1)*(c2-cmid)==cnt)
        {
            findTreasure(rmid+1,c1,r2,cmid,(r2-rmid)*(cmid-c1+1),v);
            findTreasure(r1,cmid+1,rmid,c2,(rmid-r1+1)*(c2-cmid),v);
            findTreasure(rmid+1,cmid+1,r2,c2,(r2-rmid)*(c2-cmid),v);
        }
        else if(cnt>0)
        {
            cnt-=findTreasure(rmid+1,c1,r2,cmid,0,v);
            if((r2-r1+1)*(c2-cmid)==cnt)
            {
                findTreasure(r1,cmid+1,rmid,c2,(rmid-r1+1)*(c2-cmid),v);
                findTreasure(rmid+1,cmid+1,r2,c2,(r2-rmid)*(c2-cmid),v);
            }
            else if(cnt>0)
            {
                cnt-=findTreasure(r1,cmid+1,rmid,c2,0,v);
                if(cnt>0)
                    findTreasure(rmid+1,cmid+1,r2,c2,cnt,v);
            }
        }
    }
    return rval;
}
void findTreasure (int N) {
    vii v;
    findTreasure(1,1,N,N,0,v);
    for(vii::iterator iter = v.begin(); iter!=v.end(); iter++)
        Report(iter->first,iter->second);
}

Compilation message

treasure.cpp: In function 'int findTreasure(int, int, int, int, int, vii&)':
treasure.cpp:34:13: warning: unused variable 'is_full' [-Wunused-variable]
   34 |         int is_full = false;
      |             ^~~~~~~

Subtask #1
56.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 364 KB Output is partially correct - N = 5, K = 424, score = 8
2 Partially correct 1 ms 364 KB Output is partially correct - N = 10, K = 6924, score = 4
3 Correct 1 ms 364 KB Output is correct - N = 15, K = 18267, score = 10
4 Correct 0 ms 364 KB Output is correct - N = 16, K = 18257, score = 10
5 Partially correct 1 ms 364 KB Output is partially correct - N = 55, K = 6943724, score = 1
6 Partially correct 1 ms 364 KB Output is partially correct - N = 66, K = 14820734, score = 1
7 Correct 1 ms 364 KB Output is correct - N = 77, K = 5994258, score = 10
8 Correct 1 ms 512 KB Output is correct - N = 88, K = 7883698, score = 10
9 Partially correct 1 ms 492 KB Output is partially correct - N = 99, K = 72387916, score = 1
10 Partially correct 1 ms 492 KB Output is partially correct - N = 100, K = 75967590, score = 1