oj.uz

Submission #680988

# Submission time Handle Problem Language Result Execution time Memory
680988 2023-01-12T07:53:36 Z Cross_Ratio Treasure (different grader from official contest) (CEOI13_treasure2) C++14
100 / 100
 4 ms 1236 KB 
#include <bits/stdc++.h>
#include "treasure.h"
using namespace std;
int B[105][105][4];
map<array<int, 4>, int> M;
int N;
int q(int a, int b, int c, int d) {
    if(M.count({a, b, c, d})) return M[{a, b, c, d}];
    if(a==1&&b==1&&d==N&&M.count({c+1, 1, N, N})) {
        return q(1,1,N,N) - M[{c+1, 1, N, N}];
    }
    if(b==1&&c==N&&d==N&&M.count({1,1,a-1,N})) {
        return q(1,1,N,N) - M[{1, 1, a-1, N}];
    }
    if(a==1&&b==1&&c==N&&M.count({1, d+1, N, N})) {
        return q(1,1,N,N) - M[{1, d+1, N, N}];
    }
    if(a==1&&c==N&&d==N&&M.count({1,1,N,b-1})) {
        return q(1,1,N,N) - M[{1, 1, N, b-1}];
    }
    int v = countTreasure(a, b, c, d);
    M[{a, b, c, d}] = v;
    return v;
}
void r(int a, int b) {
    Report(a, b);
}
int C[105][105];
int D[105][4];
int E[105][4];
int sum[105];
void findTreasure(int _N) {
    N = _N;
    if(N==1) {
        if(q(1, 1, 1, 1)) r(1, 1);
        return;
    }
    int d = N / 2;
    if(N%2==1) d++;
    vector<array<int, 2>> ans;
    //1 ~ d, d+1 ~ N
    int i, j;
    for(i=d;i<=N;i++) {
        for(j=d;j<=N;j++) {
            B[i][j][0] = q(1, 1, i, j);
        }
    }
    for(i=d+1;i<=N;i++) {
        for(j=d+1;j<=N;j++) {
            int v = B[i][j][0] - B[i][j-1][0] - B[i-1][j][0] + B[i-1][j-1][0];
            if(v) {
                ans.push_back({i, j});
                C[i][j] = 1;
                D[i][0]++;
                E[j][0]++;
                sum[0]++;
            }
        }
    }

    for(i=d;i<=N;i++) {
        for(j=1;j<=d;j++) {
            B[i][j][1] = q(1, j, i, N);
        }
        if(i==d) B[i][d+1][1] = q(1, d+1, N, N) - sum[0];
        else {
            B[i][d+1][1] = B[i-1][d+1][1] + D[i][0];
        }
    }
    for(i=d+1;i<=N;i++) {
        for(j=1;j<=d;j++) {
            int v = B[i][j][1] - B[i-1][j][1] - B[i][j+1][1] + B[i-1][j+1][1];
            if(v) {
                ans.push_back({i, j});
                C[i][j] = 1;
                D[i][1]++;
                E[j][1]++;
                sum[1]++;
            }
        }
    }

    for(i=1;i<=d;i++) {
        for(j=1;j<=d+1;j++) {
            B[i][j][2] = q(i, j, N, N);
        }
    }
    B[d+1][d+1][2] = sum[0];
    for(j=d;j>=1;j--) B[i][j][2] = B[i][j+1][2] + E[j][1];
    for(i=1;i<=d;i++) {
        for(j=1;j<=d;j++) {
            int v = B[i][j][2] - B[i+1][j][2] - B[i][j+1][2] + B[i+1][j+1][2];
            if(v) {
                ans.push_back({i, j});
                C[i][j] = 1;
                D[i][2]++;
                E[j][2]++;
                sum[2]++;
            }
        }
    }

    for(i=1;i<=d;i++) {
        for(j=d+1;j<=N;j++) {
            B[i][j][3] = q(i, 1, N, j);
        }
    }
    B[d+1][d][3] = sum[1];
    for(i=d;i>=1;i--) B[i][d][3] = B[i+1][d][3] + D[i][2];
    for(j=d+1;j<=N;j++) B[d+1][j][3] = B[d+1][j-1][3] + E[j][0];
    for(i=1;i<=d;i++) {
        for(j=d+1;j<=N;j++) {
            int v = B[i][j][3] - B[i+1][j][3] - B[i][j-1][3] + B[i+1][j-1][3];
            if(v) ans.push_back({i, j});
        }
    }
    for(auto it : ans) r(it[0], it[1]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct - N = 5, K = 296, score = 10
2 Correct 0 ms 340 KB Output is correct - N = 10, K = 4475, score = 10
3 Correct 0 ms 340 KB Output is correct - N = 15, K = 22366, score = 10
4 Correct 1 ms 340 KB Output is correct - N = 16, K = 28928, score = 10
5 Correct 1 ms 596 KB Output is correct - N = 55, K = 4006396, score = 10
6 Correct 2 ms 724 KB Output is correct - N = 66, K = 8305803, score = 10
7 Correct 2 ms 852 KB Output is correct - N = 77, K = 15385346, score = 10
8 Correct 3 ms 1108 KB Output is correct - N = 88, K = 26244416, score = 10
9 Correct 3 ms 1236 KB Output is correct - N = 99, K = 42035827, score = 10
10 Correct 4 ms 1236 KB Output is correct - N = 100, K = 43760000, score = 10