Submission #1133072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133072		huutuan	Navigation 2 (JOI21_navigation2)	C++20	75 / 100	758 ms	876 KiB

Anna

#include "Anna.h"
#include <vector>

#include <bits/stdc++.h>

using namespace std;

namespace Anna_solver{
   const vector<vector<int>> state={
      {0, 0, 0, 0, 0, 0, 0, 0, 0, }, 
      {0, 0, 4, 3, 3, 3, 3, 3, 3, }, 
      {0, 4, 1, 3, 3, 3, 3, 3, 3, }, 
      {1, 1, 1, 1, 1, 1, 1, 1, 1, }, 
      {2, 2, 2, 0, 0, 4, 3, 3, 3, }, 
      {2, 2, 2, 0, 4, 1, 3, 3, 3, }, 
      {2, 2, 2, 2, 2, 2, 0, 0, 4, }, 
      {2, 2, 2, 2, 2, 2, 0, 4, 1, }, 
      {2, 2, 2, 2, 2, 2, 2, 2, 2, }, 
      {2, 2, 2, 2, 2, 2, 4, 1, 1, }, 
      {2, 2, 2, 4, 1, 1, 3, 3, 3, }, 
      {3, 3, 3, 3, 3, 3, 3, 3, 3, }, 
      {4, 1, 1, 3, 3, 3, 3, 3, 3, }, 
   };
   int n;
   int get(int i, int j, int ii, int jj){
      if (i==ii && j==jj) return 4;
      if (i==ii) return (jj>j);
      return 2+(ii>i);
   }
   void solve(int N, int K, vector<int> R, vector<int> C){
      n=N;
      for (int i=0; i<n; ++i) for (int j=0; j<n; ++j){
         int id=i%3*3+j%3;
         if (id<K){
            bool check0=1, check1=1, check2=1, check3=1, check4=0;
            vector<int> v;
            for (int di=-1; di<=1; ++di) for (int dj=-1; dj<=1; ++dj){
               v.push_back(get(R[id], C[id], i+di, j+dj));
               check0&=j+dj<C[id];
               check1&=j+dj>C[id];
               check2&=i+di<R[id];
               check3&=i+di>R[id];
               check4|=get(R[id], C[id], i+di, j+dj)==4;
            }
            if (!check4){
               if (check0) for (int &k:v) k=0;
               if (check1) for (int &k:v) k=1;
               if (check2) for (int &k:v) k=2;
               if (check3) for (int &k:v) k=3;
            }
            SetFlag(i, j, 2+(find(state.begin(), state.end(), v)-state.begin()));
            assert(find(state.begin(), state.end(), v)!=state.end());
         }else SetFlag(i, j, 1);
      }
   }
} // namespace

void Anna(int N, int K, std::vector<int> R, std::vector<int> C) {
   Anna_solver::solve(N, K, R, C);
}

Bruno

#include "Bruno.h"
#include <vector>

#include <bits/stdc++.h>

using namespace std;

namespace Bruno_solver{
   const vector<vector<int>> state={
      {0, 0, 0, 0, 0, 0, 0, 0, 0, }, 
      {0, 0, 4, 3, 3, 3, 3, 3, 3, }, 
      {0, 4, 1, 3, 3, 3, 3, 3, 3, }, 
      {1, 1, 1, 1, 1, 1, 1, 1, 1, }, 
      {2, 2, 2, 0, 0, 4, 3, 3, 3, }, 
      {2, 2, 2, 0, 4, 1, 3, 3, 3, }, 
      {2, 2, 2, 2, 2, 2, 0, 0, 4, }, 
      {2, 2, 2, 2, 2, 2, 0, 4, 1, }, 
      {2, 2, 2, 2, 2, 2, 2, 2, 2, }, 
      {2, 2, 2, 2, 2, 2, 4, 1, 1, }, 
      {2, 2, 2, 4, 1, 1, 3, 3, 3, }, 
      {3, 3, 3, 3, 3, 3, 3, 3, 3, }, 
      {4, 1, 1, 3, 3, 3, 3, 3, 3, }, 
   };
   vector<int> solve(int K, vector<int> value){
      vector<vector<int>> id(3, vector<int>(3));
      for (int i=0; i<3; ++i) for (int j=0; j<3; ++j) if (value[i*3+j]==1){
         int sx=(i+1)%3;
         int sy=(j+1)%3;
         if (value[i*3+j+1]!=1) id[i][j]=8;
         else id[i][j]=7, sy=(j+2)%3;
         for (int x=0; x<3; ++x) for (int y=0; y<3; ++y){
            id[(sx+x)%3][(sy+y)%3]=x*3+y;
         }
         break;
      }
      vector<int> ans(K);
      for (int i=0; i<3; ++i) for (int j=0; j<3; ++j) if (id[i][j]<K){
         ans[id[i][j]]=state[value[i*3+j]-2][(2-i)*3+(2-j)];
      }
      return ans;
   }
} // namespace

std::vector<int> Bruno(int K, std::vector<int> value) {
   return Bruno_solver::solve(K, value);
}

• Subtask 1: 75 / 100