Submission #1217974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217974		mychecksedad	Navigation 2 (JOI21_navigation2)	C++20	100 / 100	297 ms	884 KiB

Anna

#include "Anna.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 3e6+100, M = 1e5+10, K = 52, MX = 30, FFF = 1e8+1;


namespace {

int FunctionExample(int r, int c, int K) {
  return (r + c) % K + 1;
}

} // namespace

void Anna(int n, int k, std::vector<int> R, std::vector<int> C) {
  int arr[3][3] = {
    {0, 1, 2},
    {3, 4, 5},
    {6, 7, 8}
  };
  array<array<int, 3>, 3> order = {array<int,3>{-1, -1, -1}, array<int,3>{-1, -1, -1}, array<int,3>{-1, -1, -1}};
  bool done = false;
  int X, Y;
  for(int x = 0; x < 3; ++x){
    for(int y = 0; y < 3; ++y){
      int cur = 0;
      bool bad = 0;
      for(int i = 0; i < 3; ++i){
        for(int j = 0; j < 3; ++j){
          if((i==0 && j==0) || (i==1 && j==1)) continue;
          int posx = R[cur] % 3;
          int posy = C[cur] % 3;
          if(posx == (i+x)%3 && posy == (j+y)%3){
            bad = 1;
          }
          cur++;
        }
      }
      if(!bad){
        X = x;
        Y = y;
        done = 1;
        cur = 0;
        for(int i = 0; i < 3; ++i){
          for(int j = 0; j < 3; ++j){
            if((i==0 && j==0) || (i==1 && j==1)) continue;
            int posx = R[cur] % 3;
            int posy = C[cur] % 3;
            order[(i+x)%3][(j+y)%3] = cur;
            cur++;
          }
        }
        break;
      }
    }
    if(done) break;
  }

  assert(done);

  int X2 = (X+1)%3;
  int Y2 = (Y+1)%3;
  int a = X*3 + Y;
  int b = X2*3 + Y2;
  if(a>b) swap(a, b);

  // cerr << a << ' ' << b << '\n';

  bitset<9> used;
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      int pos = order[i%3][j%3];
      if(pos != -1){
        int x_dif = R[pos] - i, y_dif = C[pos] - j;
        if(abs(x_dif) <= 1 && abs(y_dif) <= 1){
          used[(x_dif + 1) * 3 + y_dif + 1] = 1;
        }
      }
    }
  }
  int crap = 0;
  for(int i = 0; i < 9; ++i) if(!used[i] && i != 4){
    crap = i;
  }
  int crap2 = 4;
  if(crap > crap2) swap(crap, crap2);
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      int pos = order[i%3][j%3];
      if(i % 3 == X && j % 3 == Y){
        SetFlag(i, j, 12);
      }else if(i % 3 == X2 && j % 3 == Y2){
        SetFlag(i, j, (crap == 4 ? crap2 : crap) + 1);
      }else{
        int x_dif = R[pos] - i, y_dif = C[pos] - j;
        if(abs(x_dif) <= 1 && abs(y_dif) <= 1){
          int val = arr[x_dif + 1][y_dif + 1];
          if(val >= crap2) --val;
          if(val >= crap) --val;
          SetFlag(i, j, val + 1);                  
        }else{
          if(abs(y_dif) >= abs(x_dif)){
            if(y_dif > 0) SetFlag(i, j, 8);
            else SetFlag(i, j, 9);
          }else{
            if(x_dif > 0) SetFlag(i, j, 10);
            else SetFlag(i, j, 11);
          }
        }
      }
    }
  }
}

Bruno

#include "Bruno.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 3e6+100, M = 1e5+10, K = 52, MX = 30, FFF = 1e8+1;


namespace {

int variable_example = 1;

} // namespace

std::vector<int> Bruno(int k, std::vector<int> value) {
  std::vector<int> res(k, 0);
  int x = 0, y = 0;
  vector<vector<int>> v(3, vi(3));
  for(int i = 0; i < 3; ++i) for(int j =0 ; j < 3; ++j) v[i][j] = value[i*3 + j];

  for(int i = 0; i < 3; ++i){
    for(int j = 0; j < 3; ++j) if(v[i][j] == 12) x = i, y = j;
  }
  int crap = 4;
  int crap2 = (v[(x+1)%3][(y+1)%3]) - 1;
  if(crap > crap2) swap(crap, crap2);


  int arr[9][2] = {
    {-1, -1},
    {-1, 0},
    {-1, 1},
    {0, -1},
    {0, 0},
    {0, 1},
    {1, -1},
    {1, 0},
    {1, 1}
  };
  int cur = 0;
  for(int i = 0; i < 3; ++i){
    for(int j = 0; j < 3; ++j){
      if((i==0 && j==0) || (i==1 && j==1)) continue;
      int X = (i+x) % 3, Y = (j+y) % 3;

      if(v[X][Y] <= 7){
        int w = v[X][Y] - 1;
        if(w >= crap) ++w;
        if(w >= crap2) ++w;

        int new_x = arr[w][0] + X, new_y = arr[w][1] + Y;
        int x_dif = new_x - 1, y_dif = new_y - 1;
        if(x_dif == 0 && y_dif == 0) res[cur] = 4;
        else if(y_dif > 0) res[cur] = 0;
        else if(y_dif < 0) res[cur] = 1;
        else if(x_dif > 0) res[cur] = 2;
        else res[cur] = 3;
      }else{
        res[cur] = v[X][Y] - 8;
      }
      ++cur;
    }
  }

  return res;
}

• Subtask 1: 100 / 100