oj.uz

Submission #256577

# Submission time Handle Problem Language Result Execution time Memory
256577 2020-08-02T21:22:17 Z doowey Treasure (different grader from official contest) (CEOI13_treasure2) C++14
80 / 100
 9 ms 1152 KB 
#include "treasure.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

int nn;
const int NN = 105;
int disc[NN][NN];

map<pair<pii, pii>, int> vl;
int go(int i1, int j1, int i2, int j2){
    if(i1 == 0 || j1 == 0 || i2 > nn || j2 > nn || i2 == 0 || j2 == 0 || i1 > nn || j2 > nn || i1 > i2 || j1 > j2)
        return 0;
    if(vl.count(mp(mp(i1,j1), mp(i2,j2))))
        return vl[mp(mp(i1,j1), mp(i2,j2))];
    int ans = 0;
    for(int i = i1; i <= i2; i ++ ){
        for(int j = j1; j <= j2; j ++ ){
            if(disc[i][j] == -1){
                ans = -1;
                break;
            }
            ans += disc[i][j];
        }
        if(ans == -1)
            break;
    }
    if(ans == -1){
        int cnt = countTreasure(i1,j1,i2,j2);
        vl[mp(mp(i1,j1), mp(i2,j2))]=cnt;
        if(cnt == 0){
            for(int i = i1; i <= i2; i ++ ){
                for(int j = j1; j <= j2; j ++ ){
                    disc[i][j] = 0;
                }
            }
        }
        else if(cnt == (i2-i1+1) * (j2-j1+1)){
            for(int i = i1; i <= i2; i ++ ){
                for(int j = j1; j <= j2; j ++ ){
                    disc[i][j] = 1;
                }
            }
        }
        return cnt;
    }
    else
        return ans;
}

void findTreasure (int n) {
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n ; j ++ ){
            disc[i][j]=-1;
        }
    }
    nn = n;
    int l1 = 0, l2 = 0, l3 = 0, l4 = 0;
    int lef, rig;
    int up, dow;
    int cnt;
    vector<pii> shit;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            if(disc[i][j] == -1){
                lef = j;
                rig = n-j+1;
                up = i;
                dow = n-i+1;
                l1 = lef*up+(lef-1)*up+lef*(up-1)+(lef-1)*(up-1);
                l2 = rig*up+(rig-1)*up+rig*(up-1)+(rig-1)*(up-1);
                l3 = lef*dow+(lef-1)*dow+lef*(dow-1)+(lef-1)*(dow-1);
                l4 = rig*dow+(rig-1)*dow+rig*(dow-1)+(rig-1)*(dow-1);
                if(l1 >= l2 && l1 >= l3 && l1 >= l4){
                    cnt = go(1, 1, i, j) - go(1, 1, i - 1, j) - go(1, 1, i, j - 1) + go(1, 1, i - 1, j - 1);
                    if(cnt){
                        disc[i][j]=1;
                        shit.push_back(mp(i,j));
                    }
                }
                else if(l2 >= l1 && l2 >= l3 && l2 >= l4){
                    cnt = go(1, j, i, n) - go(1, j + 1, i, n) - go(1, j, i - 1, n) + go(1, j + 1, i - 1, n);
                    if(cnt){
                        disc[i][j]=1;
                        shit.push_back(mp(i,j));
                    }
                }
                else if(l3 >= l1 && l3 >= l2 && l3 >= l4){
                    cnt = go(i, 1, n, j) - go(i + 1, 1, n, j) - go(i, 1, n, j - 1) + go(i + 1, 1, n, j - 1);
                    if(cnt){
                        disc[i][j]=1;
                        shit.push_back(mp(i, j));
                    }
                }
                else{
                    cnt = go(i, j, n, n) - go(i + 1, j, n, n) - go(i, j + 1, n, n) + go(i + 1, j + 1, n, n);
                    if(cnt){
                        disc[i][j]=1;
                        shit.push_back(mp(i, j));
                    }
                }
            }
        }
    }
    for(auto p : shit)
        Report(p.fi, p.se);
}

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 384 KB Output is partially correct - N = 5, K = 495, score = 8
2 Partially correct 0 ms 384 KB Output is partially correct - N = 10, K = 5821, score = 8
3 Partially correct 1 ms 256 KB Output is partially correct - N = 15, K = 26880, score = 8
4 Partially correct 1 ms 384 KB Output is partially correct - N = 16, K = 34273, score = 8
5 Partially correct 3 ms 640 KB Output is partially correct - N = 55, K = 4217920, score = 8
6 Partially correct 4 ms 640 KB Output is partially correct - N = 66, K = 8668573, score = 8
7 Partially correct 5 ms 768 KB Output is partially correct - N = 77, K = 15962895, score = 8
8 Partially correct 8 ms 896 KB Output is partially correct - N = 88, K = 27102241, score = 8
9 Partially correct 9 ms 1128 KB Output is partially correct - N = 99, K = 43260000, score = 8
10 Partially correct 8 ms 1152 KB Output is partially correct - N = 100, K = 45017701, score = 8