Submission #475936

#	Time	Username	Problem	Language	Result	Execution time	Memory
475936		qwerasdfzxcl	Navigation 2 (JOI21_navigation2)	C++17	100 / 100	871 ms	1008 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

namespace {



} // namespace

void Anna(int N, int K, std::vector<int> R, std::vector<int> C) {
    bool chk[9];
    fill(chk, chk+9, 0);
    for (int i=0;i<K;i++){
        int num = (R[i]*3+C[i]+1)%9;
        chk[((i+10)-num)%9] = 1;
    }

    int typ = -1;
    for (int i=0;i<9;i++) if (!chk[i]) {typ = i; break;}
    assert(typ!=-1);

    fill(chk, chk+9, 0);

    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            int num = (i*3+j+typ+1)%9;
            if (!num) SetFlag(i, j, 12);
            else if (num==8) continue; //SetFlag(i, j, 1);
            else{
                num--;
                if (R[num]<i-1) SetFlag(i, j, 4);
                else if (R[num]>i+1) SetFlag(i, j, 3);
                else if (C[num]<j-1) SetFlag(i, j, 2);
                else if (C[num]>j+1) SetFlag(i, j, 1);
                else{
                    for (int x=-1, val=5;x<=1;x++){
                        for (int y=-1;y<=1;y++) if (x || y){
                            if (i+x==R[num] && j+y==C[num]){
                                chk[val-5] = 1;
                            }
                            val++;
                        }
                    }
                }
            }
        }
    }

    int typ2 = -1;
    for (int i=0;i<8;i++) if (!chk[i]) {typ2 = i; break;}
    assert(typ2!=-1);

    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            int num = (i*3+j+typ+1)%9;
            if (!num) continue;
            else if (num==8) SetFlag(i, j, typ2+1);
            else{
                num--;
                if (R[num]<i-1) continue;
                else if (R[num]>i+1) continue;
                else if (C[num]<j-1) continue;
                else if (C[num]>j+1) continue;
                else{
                    for (int x=-1, val=5;x<=1;x++){
                        for (int y=-1;y<=1;y++) if (x || y){
                            if (i+x==R[num] && j+y==C[num]){
                                if (val>typ2+5) val--;
                                SetFlag(i, j, val);
                            }
                            val++;
                        }
                    }
                }
            }
        }
    }
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

namespace {


} // namespace

std::vector<int> Bruno(int K, std::vector<int> value) {
    vector<int> ret(7);
    int pivot = -1;
    for (int i=0;i<9;i++) if (value[i]==12) pivot = i;
    assert(pivot!=-1);

    int typ2 = -1;
    for (int i=-1, k=0;i<=1;i++){
        for (int j=-1;j<=1;j++, k++){
            int num = 0;
            num += (i-pivot/3+1)*3 + (j-pivot%3+1);
            num = (num+90)%9;
            if (num==8) typ2 = value[k];
        }
    }
    typ2--;
    assert(typ2!=-1);

    for (int i=-1, k=0;i<=1;i++){
        for (int j=-1;j<=1;j++, k++){
            int num = 0;
            num += (i-pivot/3+1)*3 + (j-pivot%3+1);
            num = (num+90)%9;
            if (num==0 || num==8) continue;
            num--;
            if (value[k]<=4) ret[num] = value[k]-1;
            else{
                if (value[k]>=typ2+5) value[k]++;
                int ex = -1e9, ey = -1e9;
                for (int x=-1, val=5;x<=1;x++){
                    for (int y=-1;y<=1;y++) if (x || y){
                        if (value[k]==val) ex = i+x, ey = j+y;
                        val++;
                    }
                }
                assert(ex!=-1e9 && ey!=-1e9);
                if (ex<0) ret[num] = 3;
                else if (ex>0) ret[num] = 2;
                else if (ey<0) ret[num] = 1;
                else if (ey>0) ret[num] = 0;
                else ret[num] = 4;
            }
        }
    }
    return ret;
}

• Subtask 1: 100 / 100