제출 #1309316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309316		thewizardman	Sateliti (COCI20_satellti)	C++20	110 / 110	92 ms	126908 KiB

Main

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

int a, b;
struct i10 {
  using i7 = __uint128_t;

  i7 val[8];

  inline void shift() {
    i7 carry = b ? (val[a] >> (b-1)) : (val[a-1] >> 127);
    for (int i = a; i > 0; i--) val[i] = (val[i] << 1) | (val[i-1] >> 127);
    val[0] = (val[0] << 1) | carry;
    if (b) val[a] &= ~(((i7)1)<<b);
  }

  inline bool operator<(const i10 &other) const {
    if (b) if (val[a] != other.val[a]) return val[a] < other.val[a];
    for (int i = a-1; i >= 0; i--) if (val[i] != other.val[i]) return val[i] < other.val[i];
    return false;
  }

  inline bool operator==(const i10 &other) const {
    for (int i = a; i >= 0; i--) if (val[i] != other.val[i]) return false;
    return true;
  }
};

i10 init(const string& s) {
  i10 ret;
  memset(ret.val, 0, sizeof ret.val);
  int cur = 0;
  for (int i = 0; i < b; i++) ret.val[a] <<= 1, ret.val[a] |= (s[cur++] == '.');
  for (int i = a-1; i >= 0; i--) for (int j = 0; j < 128; j++) ret.val[i] <<= 1, ret.val[i] |= (s[cur++] == '.');
  return ret;
}

void out(vector<i10>& val) {
  for (i10 &row: val) {
    for (int i = b-1; i >= 0; i--) {
      if ((row.val[a] >> i) & 1) cout << '.';
      else cout << '*';
    }
    for (int i = a-1; i >= 0; i--) for (int j = 127; j >= 0; j--) {
      if ((row.val[i] >> j) & 1) cout << '.';
      else cout << '*';
    }
    cout << '\n';
  }
}


int n, m;
vector<i10> cur;
vector<vector<i10>> all;
string s;

vector<i10> init(const vector<i10>& v) {
  int i = 0, j = 1, k = 0;
  while (i < n && j < n && k < n) {
    const i10& a = v[(i+k)%n];
    const i10& b = v[(j+k)%n];
    if (a == b) k++;
    else if (a < b) {
      j += k+1;
      if (j == i) j++;
      k = 0;
    } else {
      i += k+1;
      if (i == j) i++;
      k = 0;
    }
  }
  int st = min(i, j);
  vector<i10> res(n);
  for (int i = 0; i < n; i++) res[i] = v[(st+i)%n];
  return res;
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> m;
  a = m/128;
  b = m%128;
  for (int i = 0; i < n; i++) {
    cin >> s;
    cur.push_back(init(s));
  }
  cur = init(cur);
  all.push_back(cur);
  for (int i = 0; i < m-1; i++) {
    for (i10 &e: cur) e.shift();
    cur = init(cur);
    all.push_back(cur);
  }
  // for (auto &e: all) out(e), cout << '\n';
  for (auto &e: all) if (e < cur) e.swap(cur);
  out(cur);
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60