제출 #1133092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133092		huutuan	Navigation 2 (JOI21_navigation2)	C++20	100 / 100	753 ms	928 KiB

Anna

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

#include <bits/stdc++.h>

using namespace std;

namespace Anna_solver{
   const vector<vector<int>> state={
      {4, 1, 1, 3, 3, 3, 3, 3, 3, },
      {0, 4, 1, 3, 3, 3, 3, 3, 3, }, 
      {0, 0, 4, 3, 3, 3, 3, 3, 3, }, 
      {2, 2, 2, 4, 1, 1, 3, 3, 3, }, 
      // {2, 2, 2, 0, 4, 1, 3, 3, 3, }, 
      {2, 2, 2, 0, 0, 4, 3, 3, 3, }, 
      {2, 2, 2, 2, 2, 2, 4, 1, 1, }, 
      {2, 2, 2, 2, 2, 2, 0, 4, 1, }, 
      {2, 2, 2, 2, 2, 2, 0, 0, 4, }, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, }, 
      {1, 1, 1, 1, 1, 1, 1, 1, 1, }, 
      {2, 2, 2, 2, 2, 2, 2, 2, 2, }, 
      {3, 3, 3, 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);
   }
   int a[110][110];
   void solve(int N, int K, vector<int> R, vector<int> C){
      memset(a, 0, sizeof a);
      int tx=0, ty=0;
      for (int i=0; i<3; ++i) for (int j=0; j<3; ++j){
         bool check=1;
         for (int x=0; x<3; ++x) for (int y=0; y<3; ++y){
            int id=(x+i)%3*3+(y+j)%3;
            if (id<K){
               check&=R[id]%3!=x || C[id]%3!=y;
            }
         }
         if (check) tx=i, ty=j;
      }
      n=N;
      for (int i=0; i<n; ++i) for (int j=0; j<n; ++j){
         int id=(i+tx)%3*3+(j+ty)%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;
            }
            a[i][j]=2+(find(state.begin(), state.end(), v)-state.begin());
            assert(find(state.begin(), state.end(), v)!=state.end());
         }else if (id==8) a[i][j]=1;
      }
      vector<int> used(8);
      for (int i=0; i<n; ++i) for (int j=0; j<n; ++j){
         if (2<=a[i][j] && a[i][j]<=9) used[a[i][j]-2]=1;
      }
      int val=find(used.begin(), used.end(), 0)-used.begin()+2;
      for (int i=0; i<n; ++i) for (int j=0; j<n; ++j){
         if (a[i][j]==0) a[i][j]=val;
         else if (a[i][j]>val) --a[i][j];
         SetFlag(i, j, a[i][j]);
      }
   }
} // 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={
      {4, 1, 1, 3, 3, 3, 3, 3, 3, },
      {0, 4, 1, 3, 3, 3, 3, 3, 3, }, 
      {0, 0, 4, 3, 3, 3, 3, 3, 3, }, 
      {2, 2, 2, 4, 1, 1, 3, 3, 3, }, 
      // {2, 2, 2, 0, 4, 1, 3, 3, 3, }, 
      {2, 2, 2, 0, 0, 4, 3, 3, 3, }, 
      {2, 2, 2, 2, 2, 2, 4, 1, 1, }, 
      {2, 2, 2, 2, 2, 2, 0, 4, 1, }, 
      {2, 2, 2, 2, 2, 2, 0, 0, 4, }, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, }, 
      {1, 1, 1, 1, 1, 1, 1, 1, 1, }, 
      {2, 2, 2, 2, 2, 2, 2, 2, 2, }, 
      {3, 3, 3, 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;
         id[i][j]=8;
         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;
      }
      int val=0;
      for (int i=0; i<3; ++i) for (int j=0; j<3; ++j) if (id[i][j]==7) val=value[i*3+j];
      for (int i=0; i<3; ++i) for (int j=0; j<3; ++j) if (id[i][j]!=7 && value[i*3+j]>=val) ++value[i*3+j];
      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: 100 / 100