oj.uz

Submission #117189

# Submission time Handle Problem Language Result Execution time Memory
117189 2019-06-15T08:50:10 Z JohnTitor Treasure (different grader from official contest) (CEOI13_treasure2) C++11
68 / 100
 3 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Treasure"
#include "treasure.h"
int ask(int x0, int y0, int x1, int y1){
    return countTreasure(x0, y0, x1, y1);
//    printf("%d %d %d %d\n", x0, y0, x1, y1);
//    fflush(stdout);
//    int ans=0;
//    read(ans);
//    return ans;
}
int c[101][101];
void solve(int x0, int y0, int x1, int y1, int sum){
    if(sum==0) return;
    if(sum==(x1-x0+1)*(y1-y0+1)){
        FOR(i, x0, x1) FOR(j, y0, y1) c[i][j]=1;
        return;
    }
    else{
        if(x1-x0>y1-y0){
            int mx=(x1+x0)/2;
            int half=ask(x0, y0, mx, y1);
            solve(x0, y0, mx, y1, half);
            solve(mx+1, y0, x1, y1, sum-half);
        }
        else{
            int my=(y1+y0)/2;
            int half=ask(x0, y0, x1, my);
            solve(x0, y0, x1, my, half);
            solve(x0, my+1, x1, y1, sum-half);
        }
    }
}
void findTreasure(int n){
//    #ifdef Aria
//        if(fopen(taskname".in", "r"))
//            freopen(taskname".in", "r", stdin);
//    #endif // Aria
    solve(1, 1, n, n, ask(1, 1, n, n));
//    puts("END");
//    FOR(i, 1, n){
//        FOR(j, 1, n) putchar(c[i][j]+'0');
//        putchar('\n');
//    }
    FOR(i, 1, n){
        FOR(j, 1, n) if(c[i][j]) Report(i, j);
    }
//    fflush(stdout);
}

Subtask #1
68.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 384 KB Output is partially correct - N = 5, K = 380, score = 8
2 Partially correct 2 ms 384 KB Output is partially correct - N = 10, K = 6426, score = 4
3 Correct 2 ms 384 KB Output is correct - N = 15, K = 16762, score = 10
4 Correct 2 ms 384 KB Output is correct - N = 16, K = 14778, score = 10
5 Partially correct 2 ms 384 KB Output is partially correct - N = 55, K = 6533585, score = 4
6 Partially correct 2 ms 384 KB Output is partially correct - N = 66, K = 13929687, score = 4
7 Correct 2 ms 384 KB Output is correct - N = 77, K = 5460074, score = 10
8 Correct 2 ms 384 KB Output is correct - N = 88, K = 7209518, score = 10
9 Partially correct 3 ms 512 KB Output is partially correct - N = 99, K = 69557120, score = 4
10 Partially correct 2 ms 412 KB Output is partially correct - N = 100, K = 72999285, score = 4