Submission #1037210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037210		hotboy2703	Navigation 2 (JOI21_navigation2)	C++17	100 / 100	647 ms	1632 KiB

Anna

#include "Anna.h"
#include<bits/stdc++.h>
using ll = long long;     
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair

void Anna(int N, int K, std::vector<int> R, std::vector<int> C) {
    ll type[3][3];
    bool oc[3][3];
    for (ll i = 0;i < 3;i ++)for (ll j = 0;j < 3;j ++)oc[i][j] = 0;
    for (ll i = 0;i < K;i ++){oc[R[i]%3][C[i]%3] = 1;}
    vector <pll> tmp;
    for (ll i = 0;i < 3;i ++)for (ll j = 0;j < 3;j ++){
        if (oc[i][j] == 0)tmp.push_back(MP(i,j));
    }
    pll dist;
    dist.fi = (tmp[1].fi-tmp[0].fi+3)%3;
    if (dist.fi==2)dist.fi = -1;
    dist.se = (tmp[1].se-tmp[0].se+3)%3;
    if (dist.se==2)dist.se = -1;
    if (dist < MP(0LL,0LL))swap(tmp[0],tmp[1]);
    for (ll i = 0;i < 3;i ++){
        for (ll j = 0;j < 3;j ++){
            ll x = (i - tmp[0].fi + 3) % 3;
            ll y = (j - tmp[0].se + 3) % 3;
            type[i][j] = x*3+y;
        }
    }
    ll A = 0,B = type[tmp[1].fi][tmp[1].se];
    vector <ll> p(9);
    for (ll i = 0,ptr = 0;i < 9;i ++){
        if (i==A||i==B)continue;
        p[i] = ptr++;
    }
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            ll t = type[r%3][c%3];
            ll id = p[t];
            if (t==A||t==B){
                SetFlag(r,c,12);
            }
            else{
                ll res = -1;
                if (abs(R[id] - r) >= 2){
                    if (R[id] > r)res = 10;
                    else res = 11;
                }
                else if (abs(C[id] - c) >= 2){
                    if (C[id] > c)res = 8;
                    else res = 9; 
                }
                else{
                    for (ll i = -1,ptr = 1;i <= 1;i ++){
                        for (ll j = -1;j <= 1;j ++){
                            ll x = (i + t/3 + 3) % 3;
                            ll y = (j + t%3 + 3) % 3;
                            ll t1 = x*3+y;
                            if (t1==A||t1==B)continue;
                            if (R[id] == r + i && C[id] == c + j){
                                res = ptr;
                            }
                            ptr++;
                        }
                    }
                }
                SetFlag(r,c,res);
            }
        }
    }
}

Bruno

#include "Bruno.h"
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair


std::vector<int> Bruno(int K, std::vector<int> value) {
    vector <vector <ll > > val(3,vector <ll> (3));
    for (ll i = 0;i < 9;i ++)val[i/3][i%3] = value[i];
    vector <vector <ll> > type(3,vector<ll> (3));
    vector <pll> tmp;
    for (ll i = 0;i < 3;i ++){
        for (ll j = 0;j < 3;j ++){
            if (val[i][j] == 12){
                tmp.push_back(MP(i,j));
            }
        }
    }
    pll dist;
    dist.fi = (tmp[1].fi-tmp[0].fi+3)%3;
    if (dist.fi==2)dist.fi = -1;
    dist.se = (tmp[1].se-tmp[0].se+3)%3;
    if (dist.se==2)dist.se = -1;
    if (dist < MP(0LL,0LL))swap(tmp[0],tmp[1]);
    for (ll i = 0;i < 3;i ++){
        for (ll j = 0;j < 3;j ++){
            ll x = (i - tmp[0].fi + 3) % 3;
            ll y = (j - tmp[0].se + 3) % 3;
            type[i][j] = x*3+y;
        }
    }
    ll A = 0,B = type[tmp[1].fi][tmp[1].se];
    vector <ll> p(9);
    for (ll i = 0,ptr = 0;i < 9;i ++){
        if (i==A||i==B)continue;
        p[i] = ptr++;
    }
    // for (ll i = 0;i < 3;i ++){
    //     for (ll j = 0;j < 3;j ++)cout<<val[i][j]<<' ';
    //     cout<<'\n';
    // }
    vector <int> res(K);
    for (ll i = 0;i < 3;i ++){
        for (ll j = 0;j < 3;j ++){
            ll t = type[i][j];
            ll id = p[t];
            if (t==A||t==B)continue;
            
           
            auto &ans = res[id];
            if (val[i][j] <= 7){ 
                ll ni,nj;
                for (ll i1 = -1,ptr = 1;i1 <= 1;i1 ++){
                    for (ll j1 = -1;j1 <= 1;j1 ++){
                        ll x = (i1 + t/3 + 3) % 3;
                        ll y = (j1 + t%3 + 3) % 3;
                        ll t1 = x*3+y;
                        if (t1==A||t1==B)continue;
                        if (ptr == val[i][j]){
                            ni = i + i1,nj = j + j1;
                        }
                        ptr++;
                    }
                }
                if (nj > 1)ans = 0;
                else if (nj < 1)ans = 1;
                else if (ni > 1)ans = 2;
                else if (ni < 1)ans = 3;
                else ans = 4;
            }
            else{
                ans = val[i][j] - 8;
            }
        }
    }
    return res;
}

Compilation message (stderr)

Bruno.cpp: In function 'std::vector<int> Bruno(int, std::vector<int>)':
Bruno.cpp:73:22: warning: 'nj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |                 else if (nj < 1)ans = 1;
      |                      ^~
Bruno.cpp:75:22: warning: 'ni' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |                 else if (ni < 1)ans = 3;
      |                      ^~

• Subtask 1: 100 / 100