Submission #387543

#	Time	Username	Problem	Language	Result	Execution time	Memory
387543		SorahISA	Navigation 2 (JOI21_navigation2)	C++17	100 / 100	1030 ms	1280 KiB

Anna

#pragma GCC optimize("Ofast", "unroll-loops")
#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

namespace {

int used[15], minUnused = 1;

int check(int nx, int ny, int gx, int gy) {
    if (abs(nx - gx) <= 1 and abs(ny - gy) <= 1) {
        int val = 3 * (gx-nx+1) + (gy-ny+1) + 1;
        return val;
    }
    if (ny+1 < gy) return 10;
    if (gy < ny-1) return 11;
    if (nx+1 < gx) return 12;
    if (gx < nx-1) return 13;
}

} // namespace

void Anna(int N, int K, vector<int> R, vector<int> C) {
    vector<vector<int>> flag;
    for (int k = 0; k < 9; ++k) {
        flag.assign(N, vector<int>(N, 0));
        memset(used, 0x00, sizeof(used)), minUnused = 1;
        
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                int p = 3 * ((r+k/3) % 3) + ((c+k%3) % 3);
                if (p == 0) flag[r][c] = 14;
                if (1 <= p and p <= 7) flag[r][c] = check(r, c, R[p-1], C[p-1]);
                if (1 <= flag[r][c] and flag[r][c] <= 9) {
                    used[flag[r][c]] = 1;
                    // cerr << "(" << r << "," << c << "): " << flag[r][c] << "\n";
                }
            }
        }
        
        if (used[9]) continue; /// main difference from L = 13
        else {
            while (used[minUnused]) ++minUnused;
            // cerr << "minUnused:  " << minUnused << "\n";
            break;
        }
    }
    
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) flag[r][c] = flag[r][c] ? flag[r][c] : minUnused;
    }
    
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            if (flag[r][c] >= 10) --flag[r][c];
            if (flag[r][c] > minUnused) --flag[r][c];
            SetFlag(r, c, flag[r][c]);
        }
    }
    
    // for (int r = 0; r < N; ++r) {
        // for (int c = 0; c < N; ++c) cerr << flag[r][c] << " \n"[c == N-1];
    // }
}

/*
11
100 7 45 45 55 55 65 65 37 29 48 16 45 44 46 45 55 65
100 7 45 45 55 55 65 65 37 29 48 16 45 44 46 45 65 55
100 7 45 45 55 55 65 65 37 29 48 16 45 44 46 45 45 55
100 7 45 45 55 55 65 65 37 29 48 16 45 44 46 45 55 45
100 7 45 45 55 55 65 65 37 29 48 16 45 44 46 45 45 64
100 7 45 45 55 55 65 65 37 29 48 16 45 44 46 45 45 65
100 7 45 45 55 55 65 65 37 29 48 16 45 44 46 45 65 45
100 7 45 45 55 55 65 65 37 29 48 16 45 44 46 45 45 54
100 7 45 45 55 55 65 65 37 29 48 16 45 44 46 45 54 45
100 7 45 45 55 55 65 65 37 29 48 16 45 44 46 45  1 98
100 7 39 48 67 19 35 29 88 60 95 12 47 71  3 86 24 19
*/

Bruno

#pragma GCC optimize("Ofast", "unroll-loops")
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

namespace {

int minUnused = 0;

vector<int> renumerate(vector<int> v) {
    vector<int> ret(9, -1);
    int p = -1;
    for (int i = 0; i < 9; ++i) if (v[i] == 12) p = i;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (i == 0 and j == 0) continue;
            if (i == 2 and j == 2) {
                minUnused = v[3*((p/3+i)%3)+((p%3+j)%3)];
                continue;
            }
            ret[3*((p/3+i)%3)+((p%3+j)%3)] = 3*i+j-1;
        }
    }
    return ret;
}

} // namespace

vector<int> Bruno(int K, vector<int> v) {
    /// +x, -x, +y, -y, 0 ///
    // cerr << "Original:   "; for (auto x : v) cerr << x << " "; cerr << "\n";
    vector<int> id = renumerate(v);
    // cerr << "Renumerate: "; for (auto x : id) cerr << x << " "; cerr << "\n";
    // cerr << "minUnused:  " << minUnused << "\n";
    vector<int> res(K, -1);
    for (int i = 0; i < 9; i++) {
        if (id[i] == -1) continue;
        if (v[i] >= 8) res[id[i]] = v[i] - 8;
        else {
            v[i] += v[i] >= minUnused, --v[i];
            int dx = (i/3 - 1) + (v[i]/3 - 1), dy = (i%3 - 1) + (v[i]%3 - 1);
                 if (dy > 0) res[id[i]] = 0;
            else if (dy < 0) res[id[i]] = 1;
            else if (dx > 0) res[id[i]] = 2;
            else if (dx < 0) res[id[i]] = 3;
            else if (dx == 0 and dy == 0) res[id[i]] = 4;
        }
    }
    // for (auto x : res) cerr << x << " "; cerr << "\n";
    return res;
}

Compilation message (stderr)

Anna.cpp: In function 'int {anonymous}::check(int, int, int, int)':
Anna.cpp:31:1: warning: control reaches end of non-void function [-Wreturn-type]
   31 | }
      | ^

• Subtask 1: 100 / 100