제출 #1143830

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

Anna

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

const int dx[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1}, dy[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};

bool used[9];

bool check(int N, int K, vector <int> R, vector <int> C, int px, int py){
  for (int x = 0; x < N; x++)
    for (int y = 0; y < N; y++){
      int tmpx = (x-px+3)%3, tmpy = (y-py+3)%3, id = tmpx*3+tmpy;
      if (id >= K) continue;
      if (R[id] == x+dx[8] && C[id] == y+dy[8]) return 0;
    }
  return 1;
}

void process(int N, int K, vector <int> R, vector <int> C, int px, int py){
  memset(used, 0, sizeof(used));
  for (int i = 0; i < K; i++){
    for (int j = 0; j < 8; j++){
      int x = R[i]-dx[j], y = C[i]-dy[j];
      if (x < 0 || x >= N || y < 0 || y >= N) continue;
      int tmpx = (x-px+3)%3, tmpy = (y-py+3)%3, id = tmpx*3+tmpy;
      if (id != i) continue;
      used[j] = 1;
    }
  }
  int unused_number = -1;
  for (int i = 0; i < 8; i++)
    if (used[i] == 0){
      unused_number = i;
      break;
    }

  for (int x = 0; x < N; x++)
    for (int y = 0; y < N; y++){
      int tmpx = (x-px+3)%3, tmpy = (y-py+3)%3, id = tmpx*3+tmpy;
      if (id == K+1) SetFlag(x, y, 12);
      else if (id == K) SetFlag(x, y, unused_number+1);
      else{
        if (R[id] < x-1) SetFlag(x, y, 8);
        else if (C[id] < y-1) SetFlag(x, y, 9);
        else if (C[id] > y+1) SetFlag(x, y, 10);
        else if (R[id] > x+1) SetFlag(x, y, 11);
        else{
          for (int i = 0; i < 8; i++)
            if (R[id] == x+dx[i] && C[id] == y+dy[i]){
              if (i < unused_number) SetFlag(x, y, i+1);
              else SetFlag(x, y, i);
            }
        }
      }
    }
}

void Anna(int N, int K, vector <int> R, vector <int> C){
  for (int px = 0; px < 3; px++)
    for (int py = 0; py < 3; py++){
      if (check(N, K, R, C, px, py)){
        process(N, K, R, C, px, py);
        return;
      }
    }
}

Bruno

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

const int dx[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1}, dy[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};

vector <int> Bruno(int K, vector <int> value){
  int px = -1, py = -1;
  for (int i = 0; i < 9; i++)
    if (value[i] == 12){
      if (dx[i] == 1) px = -1; else px = dx[i]+1;
      if (dy[i] == 1) py = -1; else py = dy[i]+1;
      break;
    }

  int unused_number = -1;
  for (int i = 0; i < 9; i++){
    int tmpx = (dx[i]-px+3)%3, tmpy = (dy[i]-py+3)%3, id = tmpx*3+tmpy;
    if (id == K){
      unused_number = value[i]-1;
      break;
    }
  }

  vector <int> res(K);
  for (int i = 0; i < 9; i++){
    int tmpx = (dx[i]-px+3)%3, tmpy = (dy[i]-py+3)%3, id = tmpx*3+tmpy;
    if (id >= K) continue;
    if (value[i] == 8) res[id] = 3;
    else if (value[i] == 9) res[id] = 1;
    else if (value[i] == 10) res[id] = 0;
    else if (value[i] == 11) res[id] = 2;
    else{
      value[i]--;
      int resx, resy;
      if (value[i] >= unused_number) value[i]++;

      resx = dx[i]+dx[value[i]], resy = dy[i]+dy[value[i]];

      if (resy > 0) res[id] = 0;
      else if (resy < 0) res[id] = 1;
      else if (resx > 0) res[id] = 2;
      else if (resx < 0) res[id] = 3;
      else res[id] = 4; 
    }
  }
  return res;
}

• Subtask 1: 100 / 100