Submission #1133104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133104		adaawf	Navigation 2 (JOI21_navigation2)	C++20	100 / 100	307 ms	1012 KiB

Anna

#include <iostream>
#include <vector>
#include <cstring>
#include "Anna.h"
using namespace std;
int aa[105][105], bb[105][105], f[105][105], dd[105];
void Anna(int n, int k, vector<int> r, vector<int> c) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int h = (i % 3) * 3 + (j % 3);
            bb[i][j] = aa[i][j] = h;
            f[i][j] = 0;
        }
    }
    memset(dd, 0, sizeof dd);
    int fl = 0;
    for (int jj = 0; jj < 3; jj++) {
        for (int kk = 0; kk < 3; kk++) {
            int flag = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (aa[i][j] >= 7) continue;
                    if (r[aa[i][j]] == i && c[aa[i][j]] == j) {
                        flag = 1;
                    }
                }
            }
            if (flag == 0) {
                fl = 1;
                break;
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    aa[i][j]++;
                    if (aa[i][j] % 3 == 0) aa[i][j] -= 3;
                }
            }
        }
        if (fl == 1) break;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                aa[i][j] += 3;
                aa[i][j] %= 9;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int h = aa[i][j];
            if (h == 8) {
                f[i][j] = 13;
            }
            else if (h != 7) {
                int x = r[h], y = c[h];
                if (abs(x - i) > abs(y - j)) {
                    if (abs(x - i) == 1) {
                        if (x < i) f[i][j] = 4;
                        else f[i][j] = 3;
                    }
                    else {
                        if (x < i) f[i][j] = 12;
                        else f[i][j] = 11;
                    }
                }
                else {
                    if (abs(x - i) == 1 && abs(y - j) == 1) {
                        if (x < i && y < j) f[i][j] = 5;
                        if (x > i && y < j) f[i][j] = 6;
                        if (x < i && y > j) f[i][j] = 7;
                        if (x > i && y > j) f[i][j] = 8;
                    }
                    else if (abs(y - j) == 1) {
                        if (y > j) f[i][j] = 1;
                        else f[i][j] = 2;
                    }
                    else {
                        if (y > j) f[i][j] = 9;
                        else f[i][j] = 10;
                    }
                }
            }
            dd[f[i][j]] = 1;
        }
    }
    int h;
    for (int i = 1; i <= 13; i++) {
        if (dd[i] == 0) {
            h = i;
            break;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (aa[i][j] == 7) SetFlag(i, j, h);
            else if (f[i][j] > h) SetFlag(i, j, f[i][j] - 1);
            else SetFlag(i, j, f[i][j]);
        }
    }
}

Bruno

#include <iostream>
#include <vector>
#include "Bruno.h"
using namespace std;
int b[3][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}}, a[4][4];
int dx[] = {0, 0, 0, 1, -1, -1, 1, -1, 1}, dy[] = {0, 1, -1, 0, 0, -1, -1, 1, 1};
vector<int> Bruno(int k, vector<int> aa) {
    vector<int> res(7);
    int fl = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (aa[i * 3 + j] == 12) {
                int h = (j + 2) % 3 + i * 3;
                h = aa[h];
                for (int k = 0; k < aa.size(); k++) {
                    if (aa[k] >= h) aa[k]++;
                }
                for (int k = 0; k < 3; k++) {
                    for (int l = 0; l < 3; l++) {
                        a[k][l] = b[(k + 2 - i) % 3][(l + 2 - j) % 3];
                    }
                }
                fl = 1;
                break;
            }
        }
        if (fl == 1) break;
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (a[i][j] >= 7) continue;
            if (aa[i * 3 + j] > 8) res[a[i][j]] = aa[i * 3 + j] - 9;
            else {
                int x = i + dx[aa[i * 3 + j]], y = j + dy[aa[i * 3 + j]];
                if (x == 1 && y == 1) res[a[i][j]] = 4;
                else if (y < 1) res[a[i][j]] = 1;
                else if (y > 1) res[a[i][j]] = 0;
                else if (x < 1) res[a[i][j]] = 3;
                else res[a[i][j]] = 2;
            }
        }
    }
    return res;
}

• Subtask 1: 100 / 100