oj.uz

Submission #270607

# Submission time Handle Problem Language Result Execution time Memory
270607 2020-08-17T19:49:20 Z johutha Treasure (different grader from official contest) (CEOI13_treasure2) C++17
69 / 100
 1 ms 512 KB 
#include <iostream>
#include <vector>
#include <memory>
#include "treasure.h"

#define int int64_t

using namespace std;

int n;

pair<int,int> rotate(pair<int,int> p, int rot)
{
    if (rot == 1) return make_pair(p.second, n - 1 - p.first);
    if (rot == 2) return make_pair(n - 1 - p.first, n - 1 - p.second);
    if (rot == 3) return make_pair(n - 1 - p.second, p.first);
    return p;
}

int query(int y1, int x1, int y2, int x2, int rot)
{
    tie(y1, x1) = rotate(make_pair(y1, x1), rot);
    tie(y2, x2) = rotate(make_pair(y2, x2), rot);
    return countTreasure(min(y1, y2) + 1, min(x1, x2) + 1, max(y1, y2) + 1, max(x1, x2) + 1);
}

void findTreasure (signed N)
{
    n = N;

    vector<int> ar = {n / 2, n - (n / 2)};

    vector<vector<int>> res(n, vector<int>(n, -1));

    for (int rt = 0; rt < 4; rt++)
    {
        int r = ar[rt / 2];
        int c = ar[(rt / 2 == 1) ^ (rt % 2 == 0)];
        
        vector<vector<int>> qr(r + 1, vector<int>(c + 1, -1));

        for (int i = 0; i <= r; i++)
        {
            for (int j = 0; j <= c; j++)
            {
                int y = n - r - 1 + i;
                int x = n - c - 1 + j;
                qr[i][j] = query(y, x, 0, 0, rt);
            }
        }

        for (int i = 0; i < r; i++)
        {
            for (int j = 0; j < c; j++)
            {
                int y = n - r + i;
                int x = n - c + j;
                tie(y, x) = rotate(make_pair(y, x), rt);
                res[y][x] = qr[i][j] + qr[i + 1][j + 1] - qr[i + 1][j] - qr[i][j + 1];
            }
        }
    }
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (res[i][j] == 1) Report(i + 1, j + 1);
        }
    }
}

Subtask #1
69.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 384 KB Output is partially correct - N = 5, K = 598, score = 1
2 Partially correct 0 ms 384 KB Output is partially correct - N = 10, K = 6444, score = 4
3 Partially correct 0 ms 384 KB Output is partially correct - N = 15, K = 28833, score = 8
4 Partially correct 0 ms 384 KB Output is partially correct - N = 16, K = 36612, score = 8
5 Partially correct 1 ms 384 KB Output is partially correct - N = 55, K = 4304273, score = 8
6 Partially correct 1 ms 384 KB Output is partially correct - N = 66, K = 8816812, score = 8
7 Partially correct 1 ms 384 KB Output is partially correct - N = 77, K = 16197286, score = 8
8 Partially correct 1 ms 384 KB Output is partially correct - N = 88, K = 27450900, score = 8
9 Partially correct 1 ms 512 KB Output is partially correct - N = 99, K = 43755201, score = 8
10 Partially correct 1 ms 512 KB Output is partially correct - N = 100, K = 45527904, score = 8