Submission #418080

#	Time	Username	Problem	Language	Result	Execution time	Memory
418080		Mamnoon_Siam	Navigation 2 (JOI21_navigation2)	C++17	75 / 100	767 ms	884 KiB

Anna

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

using ii = pair<int, int>;
using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
#define fi first
#define se second
#define all(v) begin(v), end(v)
#define sz(v) (int)(v.size())

#ifndef LOCAL
#define debug(...)
#endif

namespace {
#ifdef LOCAL
  template<typename T>
  string to_string(T x) {
    return std::to_string(x);
  }
  template<typename A, typename B>
  string to_string(pair<A, B> pa) {
    return "(" + to_string(pa.first) + "," + to_string(pa.second) + ")";
  }

  string to_string(string s) {
    return "\"" + s + "\"";
  }

  template<typename T>
  string to_string(vector<T> v) {
    bool first = true;
    string ret = "{";
    for(int i = 0; i < (int)v.size(); ++i) {
      if(!first) ret += ", ";
      ret += to_string(v[i]);
      first = false;
    }
    ret += "}";
    return ret;
  }

  void debug_out() {
    cerr << endl;
  }

  template<typename Head, typename... Tail>
  void debug_out(Head _H_, Tail... _T_) {
    cerr << " " << to_string(_H_);
    debug_out(_T_...);
  }

  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
  #define debug(...)
#endif
  const int neix[] = {-1, -1, -1, 0, 0, 0, +1, +1, +1};
  const int neiy[] = {-1, 0, +1, -1, 0, +1, -1, 0, +1};
  int get_action(int x1, int y1, int x2, int y2) {
    if(x1 == x2 and y1 == y2) return 4;
    if(x2 <= x1 and y2 <= y1) {
      if(x1 - x2 >= y1 - y2) return 3;
      return 1;
    }
    if(x2 <= x1 and y2 > y1) {
      if(x1 - x2 >= y2 - y1) return 3;
      return 0;
    }
    if(x2 > x1 and y2 <= y1) {
      if(x2 - x1 >= y1 - y2) return 2;
      return 1;
    }
    if(x2 > x1 and y2 > y1) {
      if(x2 - x1 >= y2 - y1) return 2;
      return 0;
    }
  }
} // namespace

void Anna(int N, int K, std::vector<int> R, std::vector<int> C) {
  for(int r = 0; r < N; ++r) {
    for(int c = 0; c < N; ++c) {
      int k = 3 * (r % 3) + c % 3;
      debug(r, c, k);
      int value = 0;
      if(k < K) {
        if(max(abs(R[k] - r), abs(C[k] - c)) <= 1) {
          for(int i = 0; i < 9; ++i) {
            if(R[k] - r == neix[i] and C[k] - c == neiy[i]) {
              value = i;
            }
          }
        } else {
          value = get_action(r, c, R[k], C[k]) + 9;
        }
      } else if(k == 8) {
        value = 13;
      }
      SetFlag(r, c, value + 1);
    }
  }
}

Bruno

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

using ii = pair<int, int>;
using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
#define fi first
#define se second
#define all(v) begin(v), end(v)
#define sz(v) (int)(v.size())

namespace {
#ifdef LOCAL
  template<typename T>
  string to_string(T x) {
    return std::to_string(x);
  }
  template<typename A, typename B>
  string to_string(pair<A, B> pa) {
    return "(" + to_string(pa.first) + "," + to_string(pa.second) + ")";
  }

  string to_string(string s) {
    return "\"" + s + "\"";
  }

  template<typename T>
  string to_string(vector<T> v) {
    bool first = true;
    string ret = "{";
    for(int i = 0; i < (int)v.size(); ++i) {
      if(!first) ret += ", ";
      ret += to_string(v[i]);
      first = false;
    }
    ret += "}";
    return ret;
  }

  void debug_out() {
    cerr << endl;
  }

  template<typename Head, typename... Tail>
  void debug_out(Head _H_, Tail... _T_) {
    cerr << " " << to_string(_H_);
    debug_out(_T_...);
  }

  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
  #define debug(...)
#endif
  const int neix[] = {-1, -1, -1, 0, 0, 0, +1, +1, +1};
  const int neiy[] = {-1, 0, +1, -1, 0, +1, -1, 0, +1};
  int get_action(int x1, int y1, int x2, int y2) {
    if(x1 == x2 and y1 == y2) return 4;
    if(x2 <= x1 and y2 <= y1) {
      if(x1 - x2 >= y1 - y2) return 3;
      return 1;
    }
    if(x2 <= x1 and y2 > y1) {
      if(x1 - x2 >= y2 - y1) return 3;
      return 0;
    }
    if(x2 > x1 and y2 <= y1) {
      if(x2 - x1 >= y1 - y2) return 2;
      return 1;
    }
    if(x2 > x1 and y2 > y1) {
      if(x2 - x1 >= y2 - y1) return 2;
      return 0;
    }
  }
} // namespace

vi Bruno(int K, vi value) {
  for(int& x : value) x--;
  int pivot = -1;
  for(int i = 0; i < 9; ++i) {
    if(value[i] == 13) {
      pivot = i;
    }
  }
  assert(~pivot);
  vi ans(K, -1);
  for(int i = 0; i < 9; ++i) {
    int modx = (6 + 2 + neix[i] - neix[pivot]) % 3;
    int mody = (6 + 2 + neiy[i] - neiy[pivot]) % 3;
    int k = modx * 3 + mody;
    debug(modx, mody, k);
    if(k < K) {
      int number = value[i];
      if(number >= 9) {
        ans[k] = number - 9;
      } else {
        ans[k] = get_action(0, 0, neix[i] + neix[number], neiy[i] + neiy[number]);
      }
      debug(ans[k]);
    }
  }

  assert(count(all(ans), -1) == 0);
  return ans;
}

Compilation message (stderr)

Anna.cpp: In function 'int {anonymous}::get_action(int, int, int, int)':
Anna.cpp:80:3: warning: control reaches end of non-void function [-Wreturn-type]
   80 |   }
      |   ^

Bruno.cpp: In function 'int {anonymous}::get_action(int, int, int, int)':
Bruno.cpp:76:3: warning: control reaches end of non-void function [-Wreturn-type]
   76 |   }
      |   ^

• Subtask 1: 75 / 100