제출 #1137309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137309		nathan4690	Navigation 2 (JOI21_navigation2)	C++20	100 / 100	300 ms	876 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
    using namespace std;

int findFlag(int r, int c, int tarr, int tarc, int m1, int m2){
//    cout << "!!!! " << r << ' ' << c << ' ' << tarr << ' ' << tarc << endl;
    if(max(abs(tarr - r), abs(tarc - c)) <= 1){
        int xm1 = m1 / 3, ym1 = m1 % 3, xm2 = m2 / 3, ym2 = m2 % 3;
        tarr = (tarr + 3000) % 3; tarc = (tarc + 3000) % 3;
        vector<pair<int,int>> dd = {{-1, 0}, {0, 0}, {1, 0}, {-1, -1}, {0, -1}, {1, -1}, {-1, 1}, {0, 1}, {1, 1}};
        int idx = 0;
//        cout << xm1 << ' ' << ym1 << ' ' << xm2 << ' ' << ym2 << '\n';
        for(pair<int,int> d: dd){
            int nx = (r + d.first + 3) % 3, ny = (c + d.second + 3) % 3;
            if(nx == xm1 && ny == ym1) continue;
            if(nx == xm2 && ny == ym2) continue;
            idx++;
            if(tarr == nx && tarc == ny) return idx;
        }
        assert(0);
    }
    if(tarr < r - 1) return 8;
    if(tarr > r + 1) return 10;
    if(tarc < c - 1) return 11;
    return 9;
}

void checkPos(int &m1, int &m2){
    int xa = m1 / 3, ya = m1 % 3, xb = m2 / 3, yb = m2 % 3;
    vector<pair<int,int>> dd = {{0, 1}, {1, 0}, {1, -1}, {1, 1}};
    for(pair<int,int> d: dd){
        int vx = (xb + d.first + 3) % 3, vy = (yb + d.second + 3) % 3;
        if(vx == xa && vy == ya) {
            swap(m1, m2);
            return;
        }
    }
}

bool vis[3][3];
void myMove(int &vx, int &vy){
    vis[vx][vy] = 1;
    while(vis[vx][vy]){
        vy++;
        if(vy == 3){
            vy = 0;
        }
        if(vis[vx][vy]){
            vx = (vx == 2 ? 0 : vx + 1);
        }
    }
}

} // namespace

void Anna(int N, int K, vector<int> R, vector<int> C) {
    int m1 = -1, m2 = -1;
    bool flag[9] = {false};
    for(int j=0;j<K;j++){
        flag[3 * ((R[j]) % 3) + ((C[j]) % 3)] = 1;
    }
    for(int i=0;i<9;i++){
        if(!flag[i]){
            if(m1 == -1) m1 = i;
            else if(m2 == -1){
                m2 = i;
                break;
            }
        }
    }
    checkPos(m1, m2);
    for(int x=0;x<N;x+=3){
        for(int y=0;y<N;y+=3){
            memset(vis, 0, sizeof(vis));
            int vx = m1 / 3, vy = m1 % 3;
            if(x + vx < N && y + vy < N) SetFlag(x + vx, y + vy, 12);
            for(int i=0;i<K;i++){
                myMove(vx, vy);
                if(3 * vx + vy == m2) {
                    if(x + vx < N && y + vy < N) SetFlag(x + vx, y + vy, 12);
                    myMove(vx, vy);
                }
                if(x + vx < N && y + vy < N) SetFlag(x + vx, y + vy, findFlag(vx, vy, R[i] - x, C[i] - y, m1, m2));
            }
        }
    }
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
    using namespace std;

namespace {

    using namespace std;
void checkPos(int &m1, int &m2){
    int xa = m1 / 3, ya = m1 % 3, xb = m2 / 3, yb = m2 % 3;
    vector<pair<int,int>> dd = {{0, 1}, {1, 0}, {1, -1}, {1, 1}};
    for(pair<int,int> d: dd){
        int vx = (xb + d.first + 3) % 3, vy = (yb + d.second + 3) % 3;
        if(vx == xa && vy == ya) {
            swap(m1, m2);
            return;
        }
    }
}

bool vis[3][3];
void myMove(int &vx, int &vy){
    vis[vx][vy] = 1;
    while(vis[vx][vy]){
        vy++;
        if(vy == 3){
            vy = 0;
        }
        if(vis[vx][vy]){
            vx = (vx == 2 ? 0 : vx + 1);
        }
    }
}

int findDir(int code, int r, int c, int tarr, int tarc, int m1, int m2){
//    cout << "? " << r << ' ' << c << '\n';
    if(code == 8) return 3;
    if(code == 10) return 2;
    if(code == 9) return 0;
    if(code == 11) return 1;
    int posx, posy;
    int xm1 = m1 / 3, ym1 = m1 % 3, xm2 = m2 / 3, ym2 = m2 % 3;
    vector<pair<int,int>> dd = {{-1, 0}, {0, 0}, {1, 0}, {-1, -1}, {0, -1}, {1, -1}, {-1, 1}, {0, 1}, {1, 1}};
    int idx = 0;
    for(pair<int,int> d: dd){
        int nx = (r + d.first + 3) % 3, ny = (c + d.second + 3) % 3;
        if(nx == xm1 && ny == ym1) continue;
        if(nx == xm2 && ny == ym2) continue;
        idx++;
        if(idx == code) {
            posx = r + d.first; posy = c + d.second;
            break;
        }
    }
//    cout << "!! " << r << ' ' << c << ' ' << posx << ' ' << posy << ' ' << tarr << ' ' << tarc << '\n';
    if(posx < tarr) return 3;
    if(posx > tarr) return 2;
    if(posy < tarc) return 1;
    if(posy > tarc) return 0;
    return 4;
}

} // namespace

vector<int> Bruno(int K, vector<int> value) {
    bool F[3][3];
    int V[3][3];
    int m1 = -1, m2 = -1;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            V[i][j] = value[i * 3 + j];
            if(V[i][j] == 12){
                if(m1 == -1) m1 = i * 3 + j;
                else if(m2 == -1){
                    m2 = i * 3 + j;
                }
            }
//            cout << V[i][j] << ' ';
        }
//        cout << '\n';
    }
    checkPos(m1, m2);
    int vx = m1 / 3, vy = m1 % 3;
    vector<int> res;
    memset(vis, 0, sizeof(vis));
    for(int i=0;i<K;i++){
        myMove(vx, vy);
        if(3 * vx + vy == m2) myMove(vx, vy);
        res.push_back(findDir(V[vx][vy], vx, vy, 1, 1, m1, m2));
//        cout << "! " << res.back() << '\n';
    }
    return res;
}

• Subtask 1: 100 / 100