#include <bits/stdc++.h>
template<class A, class B>
bool maximize(A &a, const B& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template<class A, class B>
bool minimize(A &a, const B& b) {
if (a > b) {
a = b;
return true;
}
return false;
}
class SignedBigInteger {
protected:
const static int BASE = 1E7;
const static int BASE_DIGIT_COUNT = 7;
static long long convertStringToInteger(const std::string &s) {
long long result;
std::stringstream value(s);
value >> result;
return result;
}
static std::string convertIntegerToString(const long long x) {
std::stringstream value;
std::string result;
value << x;
value >> result;
return result;
}
static std::string findSubstring(const std::string &s, int l, const int r) {
if (l < 0)
l = 0;
return s.substr(l, r - l + 1);
}
static std::vector<long long> addDigits(std::vector<long long> a, const std::vector<long long> &b) {
const int lengthA = a.size(), lengthB = b.size();
a.resize(std::max(lengthA, lengthB));
for (int i = 0; i < lengthB; ++i)
a[i] += b[i];
return a;
}
static std::vector<long long> subtractDigits(std::vector<long long> a, const std::vector<long long> &b) {
/**
a >= b
**/
long long remainder = 0;
const int lengthA = a.size(), lengthB = b.size();
for (int i = 0; i < lengthB; ++i) {
remainder = a[i] - b[i] - remainder;
if (remainder < 0) {
a[i] = remainder + BASE;
remainder = 1;
} else {
a[i] = remainder;
remainder = 0;
}
}
for (int i = lengthB; i < lengthA; ++i) {
remainder = a[i] - remainder;
if (remainder < 0) {
a[i] = remainder + BASE;
remainder = 1;
} else {
a[i] = remainder;
remainder = 0;
}
}
return a;
}
static int getReversedBits(int const mask, int const n) {
int result(0);
for (int i = 0; i < n; ++i)
if (mask & (1 << i))
result |= 1 << n - 1 - i;
return result;
}
static int checkPowerOfTwo(int number) {
for (; !(number & 1); number >>= 1);
return number == 1;
}
static int getNumberOfBits(int number) {
if (number == 0)
return 1;
int result{};
for (; number; number >>= 1)
++result;
return result;
}
static void fft(std::vector<std::complex<long double> > &p, bool const invert) {
const int length(p.size());
if (length == 1)
return;
const int n(getNumberOfBits(length - 1));
std::vector<std::complex<long double> > next(length), w(length);
std::complex<long double> u, v;
long double angle;
for (int x = 0, y; x < length; ++x) {
y = getReversedBits(x, n);
if (x < y)
swap(p[x], p[y]);
}
w.front() = 1;
for (int i, even, odd, span = 1; span < length; span <<= 1) {
angle = acos(-1) / span;
if (invert)
angle = -angle;
const std::complex<long double> aug(cos(angle), sin(angle));
for (i = 1; i < span; ++i)
w[i] = w[i - 1] * aug;
for (even = 0, odd = span; even < length;) {
for (i = 0; i < span; ++i) {
u = p[even + i];
v = p[odd + i] * w[i];
next[even + i] = u + v;
next[odd + i] = u - v;
}
even = odd + span;
odd = even + span;
};
for (i = 0; i < length; ++i)
p[i] = next[i];
}
if (invert) {
for (int i = 0; i < length; ++i)
p[i] /= length;
}
}
static void multiplyPolynomials(std::vector<long double> const &a, std::vector<long double> const &b, std::vector<long double> &result) {
const int lengthA(a.size()), lengthB(b.size()), length(lengthA + lengthB);
std::vector<std::complex<long double> > fa(a.begin(), a.end()), fb(b.begin(), b.end());
int n = 1;
for (; n < length; n <<= 1);
fa.resize(n);
fb.resize(n);
fft(fa, false);
fft(fb, false);
for (int i = 0; i < n; ++i)
fa[i] *= fb[i];
fft(fa, true);
result.resize(n);
for (int i = 0; i < n; ++i)
result[i] = round(fa[i].real());
}
static void multiplyPolynomials(std::vector<long long> const &a, std::vector<long long> const &b, std::vector<long long> &result) {
const int lengthA(a.size()), lengthB(b.size()), length(lengthA + lengthB - 1);
std::vector<std::complex<long double> > fa(a.begin(), a.end()), fb(b.begin(), b.end());
int n = 1;
for (; n < length; n <<= 1);
fa.resize(n);
fb.resize(n);
fft(fa, false);
fft(fb, false);
for (int i = 0; i < n; ++i)
fa[i] *= fb[i];
fft(fa, true);
result.resize(length);
for (int i = 0; i < length; ++i)
result[i] = round(fa[i].real());
}
private:
bool negative;
std::vector<long long> digits;
void fixInteger() {
long long remainder = 0;
for (long long &i : digits) {
remainder += i;
i = remainder % BASE;
remainder /= BASE;
}
for (; remainder; remainder /= BASE)
digits.push_back(remainder % BASE);
while (digits.size() > 1 && !digits.back())
digits.pop_back();
if (digits.size() == 1 && digits.front() == 0)
negative = false;
}
public:
SignedBigInteger(): negative(false), digits(1, 0) {};
SignedBigInteger(const std::string &s) {
if (s.empty())
throw std::invalid_argument("The argument must be non-empty");
const int length = s.size();
if (s.front() == '-') {
if (length == 1)
throw std::invalid_argument("The argument must contain at least one digit");
negative = true;
for (int i = length - 1; i >= 1; i -= BASE_DIGIT_COUNT)
digits.push_back(convertStringToInteger(findSubstring(s, std::max(i - BASE_DIGIT_COUNT + 1, 1), i)));
} else {
negative = false;
for (int i = length - 1; i >= 0; i -= BASE_DIGIT_COUNT)
digits.push_back(convertStringToInteger(findSubstring(s, i - BASE_DIGIT_COUNT + 1, i)));
}
fixInteger();
}
static SignedBigInteger getZero() {
SignedBigInteger result;
result.negative = false;
result.digits.resize(1);
result.digits.front() = 0;
return result;
}
static SignedBigInteger getOne() {
SignedBigInteger result;
result.negative = false;
result.digits.resize(1, 1);
result.digits.front() = 1;
return result;
}
static SignedBigInteger fromSigned32BitInteger(int number) {
if (number == 0)
return getZero();
SignedBigInteger result;
long long value;
if (number < 0) {
result.negative = true;
value = -number;
} else {
result.negative = false;
value = number;
}
for (; value; value /= BASE)
result.digits.push_back(value % BASE);
return result;
}
short getSign() const {
if (negative)
return -1;
if (digits.size() > 1 || digits.back())
return 1;
return 0;
}
bool isPositive() const {
return getSign() > 0;
}
bool isNegative() const {
return getSign() < 0;
}
SignedBigInteger findAbsoluteValue() const {
SignedBigInteger result;
result.negative = false;
result.digits = this -> digits;
return result;
}
bool isZero() const {
return getSign() == 0;
}
bool isNonZero() const {
return getSign() != 0;
}
bool isNonNegative() const {
return !negative;
}
bool isNonPositive() const {
return negative || (digits.size() == 1 && digits.back() == 0);
}
static SignedBigInteger calculateMultiplication(const SignedBigInteger &a, const SignedBigInteger &b) {
if (a.isZero() || b.isZero())
return getZero();
const int lengthA = a.digits.size(), lengthB = b.digits.size();
SignedBigInteger result;
result.negative = (a.negative != b.negative);
result.digits.resize(lengthA + lengthB + 1);
for (int x = 0, y; x < lengthA; ++x)
for (y = 0; y < lengthA; ++y)
result.digits[x + y] += a.digits[x] * b.digits[y];
result.fixInteger();
return result;
}
friend bool operator ! (const SignedBigInteger &number) {
return number.isZero();
}
friend std::ostream& operator << (std::ostream& outputStream, const SignedBigInteger &number) {
if (number.negative)
outputStream << '-';
outputStream << number.digits.back();
for (int i = (int)number.digits.size() - 2; i >= 0; --i)
outputStream << std::setfill('0') << std::setw(BASE_DIGIT_COUNT) << number.digits[i];
return outputStream;
}
friend std::istream& operator >> (std::istream& inputStream, SignedBigInteger &number) {
std::string value;
inputStream >> value;
number = SignedBigInteger(value);
return inputStream;
}
std::string toString() const {
std::string result, d;
if (negative)
result += '-';
result += convertIntegerToString(digits.back());
for (int i = (int)digits.size() - 2; i >= 0; --i) {
d = convertIntegerToString(digits.at(i));
result += std::string(BASE_DIGIT_COUNT - (int)d.size(), '0') + d;
}
return result;
}
SignedBigInteger findPower(long long e) const {
SignedBigInteger result = getOne(), base = (*this);
for (; e; e >>= 1, base = base * base)
if (e & 1)
result = result * base;
return result;
}
SignedBigInteger operator - () const {
if (this -> isZero())
return getZero();
SignedBigInteger result;
result.negative = !(this -> negative);
result.digits = this -> digits;
return result;
}
bool operator ! () {
return !(this -> isZero());
}
short compare(const SignedBigInteger &number) const {
const int lengthA = (this -> digits).size(), lengthB = number.digits.size();
if ((this -> negative) && number.negative) {
if (lengthA < lengthB)
return 1;
if (lengthA > lengthB)
return -1;
for (int i = lengthA - 1; i >= 0; --i) {
if ((this -> digits)[i] < (number.digits)[i])
return 1;
if ((this -> digits)[i] > (number.digits)[i])
return -1;
}
return 0;
}
if (this -> negative)
return -1;
if (number.negative)
return 1;
if (lengthA < lengthB)
return -1;
if (lengthA > lengthB)
return 1;
for (int i = lengthB - 1; i >= 0; --i) {
if ((this -> digits)[i] < (number.digits)[i])
return -1;
if ((this -> digits)[i] > (number.digits)[i])
return 1;
}
return 0;
}
short compareByAbsoluteValues(const SignedBigInteger &number) const {
const int lengthA = (this -> digits).size(), lengthB = number.digits.size();
if (lengthA < lengthB)
return -1;
if (lengthA > lengthB)
return 1;
for (int i = lengthA - 1; i >= 0; --i) {
if ((this -> digits)[i] < (number.digits)[i])
return -1;
if ((this -> digits)[i] > (number.digits)[i])
return 1;
}
return 0;
}
friend SignedBigInteger operator - (const SignedBigInteger &a, const SignedBigInteger &b) {
return a + (-b);
}
friend SignedBigInteger operator + (const SignedBigInteger &a, const SignedBigInteger &b) {
SignedBigInteger result;
if (a.negative && b.negative) {
result.negative = true;
result.digits = addDigits(a.digits, b.digits);
} else if (a.negative) {
if (a.compareByAbsoluteValues(b) <= 0) {
result.negative = false;
result.digits = subtractDigits(b.digits, a.digits);
} else {
result.negative = true;
result.digits = subtractDigits(a.digits, b.digits);
}
} else if (b.negative) {
if (b.compareByAbsoluteValues(a) <= 0) {
result.negative = false;
result.digits = subtractDigits(a.digits, b.digits);
} else {
result.negative = true;
result.digits = subtractDigits(b.digits, a.digits);
}
} else {
result.negative = false;
result.digits = addDigits(a.digits, b.digits);
}
result.fixInteger();
return result;
}
friend bool operator == (const SignedBigInteger &a, const SignedBigInteger &b) {
if (a.negative != b.negative)
return false;
const int lengthA = a.digits.size(), lengthB = b.digits.size();
if (lengthA != lengthB)
return false;
for (int i = 0; i < lengthA; ++i)
if (a.digits[i] != b.digits[i])
return false;
return true;
}
friend bool operator != (const SignedBigInteger &a, const SignedBigInteger &b) {
if (a.negative != b.negative)
return true;
const int lengthA = a.digits.size(), lengthB = b.digits.size();
if (lengthA != lengthB)
return true;
for (int i = 0; i < lengthA; ++i)
if (a.digits[i] != b.digits[i])
return true;
return false;
}
friend bool operator < (const SignedBigInteger &a, const SignedBigInteger &b) {
return a.compare(b) < 0;
}
friend bool operator > (const SignedBigInteger &a, const SignedBigInteger &b) {
return a.compare(b) > 0;
}
friend bool operator <= (const SignedBigInteger &a, const SignedBigInteger &b) {
return a.compare(b) <= 0;
}
friend bool operator >= (const SignedBigInteger &a, const SignedBigInteger &b) {
return a.compare(b) >= 0;
}
int toSigned32BitInteger() const {
const int length = digits.size();
int result = 0;
for (int i = length - 1; i >= 0; --i)
result = result * BASE + digits[i];
if (negative)
result = -result;
return result;
}
long long toSigned64BitInteger() const {
const int length = digits.size();
long long result = 0;
for (int i = length - 1; i >= 0; --i)
result = result * BASE + digits[i];
if (negative)
result = -result;
return result;
}
friend SignedBigInteger& operator += (SignedBigInteger &a, const SignedBigInteger &b) {
a = a + b;
return a;
}
friend SignedBigInteger& operator -= (SignedBigInteger &a, const SignedBigInteger &b) {
a = a - b;
return a;
}
friend SignedBigInteger operator * (const SignedBigInteger &a, const SignedBigInteger &b) {
if (a.isZero() || b.isZero())
return getZero();
SignedBigInteger result;
result.negative = (a.negative != b.negative);
multiplyPolynomials(a.digits, b.digits, result.digits);
result.fixInteger();
return result;
}
friend SignedBigInteger& operator *= (SignedBigInteger &a, const SignedBigInteger &b) {
a = a * b;
return a;
}
std::string findBinaryRepresentation() const {
if (isZero())
return "0";
SignedBigInteger number = this -> findAbsoluteValue();
std::vector<SignedBigInteger> p(1, getOne());
std::string result;
int length = 1;
for (; p.back() <= number;) {
++length;
result += '0';
p.push_back(p.back() << 1);
}
for (int i = length - 2; i >= 0; --i)
if (number >= p[i]) {
number -= p[i];
result[i] = '1';
}
if (negative)
result += '-';
reverse(result.begin(), result.end());
return result;
}
friend SignedBigInteger operator << (const SignedBigInteger &a, const short e) {
SignedBigInteger result(a);
for (auto &d : result.digits)
d <<= e;
result.fixInteger();
return result;
}
SignedBigInteger& operator ++ () {
(*this) += getOne();
return *this;
}
SignedBigInteger operator ++ (int) {
const SignedBigInteger result = *this;
(*this) += getOne();
return result;
}
SignedBigInteger& operator -- () {
(*this) -= getOne();
return *this;
}
SignedBigInteger operator -- (int) {
const SignedBigInteger result = *this;
(*this) -= getOne();
return result;
}
};
class DisjointSet {
private:
mutable std::vector<int> root;
public:
DisjointSet() {};
DisjointSet(const int n): root(n, -1) {};
virtual ~DisjointSet() {};
void reload() {
std::fill(root.begin(), root.end(), -1);
};
int getRoot(const int x) const {
return root[x] < 0 ? x : (root[x] = getRoot(root[x]));
}
bool unite(int x, int y) {
x = getRoot(x);
y = getRoot(y);
if (x == y)
return false;
if (root[x] < root[y]) {
root[x] += root[y];
root[y] = x;
} else {
root[y] += root[x];
root[x] = y;
}
return true;
}
bool checkConnected(const int x, const int y) const {
return getRoot(x) == getRoot(y);
}
int getTreeSize(const int x) const {
return -root[getRoot(x)];
}
};
template<class T, const T MOD>
class Matrix {
protected:
static T computeAddition(T x, const T y) {
if ((x += y) >= MOD)
x -= MOD;
return x;
}
static T computeSubtraction(T x, const T y) {
if ((x -= y) < 0)
x += MOD;
return x;
}
static T computeMultiplication(const T x, const T y) {
return 1LL * x * y % MOD;
}
static T computeInverse(T b, long long e) {
T result = 1;
for (e = MOD - 2; e; e >>= 1, b = computeMultiplication(b, b))
if (e & 1)
result = computeMultiplication(result, b);
return result;
}
private:
std::vector<std::vector<T> > values;
public:
Matrix() {};
Matrix(const int n, const int m): values(n, std::vector<T>(m)) {};
static Matrix<T, MOD> getSquareZeroMatrix(const int n) {
Matrix matrix;
matrix.values.resize(n, std::vector<T>(n));
return matrix;
}
static Matrix<T, MOD> getSquareZeroMatrix(const int n, const int m) {
Matrix matrix;
matrix.values.resize(n, std::vector<T>(m));
return matrix;
}
static Matrix<T, MOD> getIdentityMatrix(const int n) {
Matrix matrix;
matrix.values.resize(n, std::vector<T>(n));
for (int i = 0; i < n; ++i)
matrix.values[i][i] = 1;
return matrix;
}
bool checkSquareMatrix() const {
return values.empty() || values.size() == values.front().size();
}
Matrix(const Matrix &matrix) {
this -> values = matrix.values;
};
Matrix& operator = (const Matrix &matrix) {
this -> values = matrix.values;
return *this;
}
template<class A, class B>
void getShape(A &n, B &m) const {
if (values.empty()) {
n = m = 0;
return;
}
n = values.size();
m = values.front().size();
}
std::pair<int, int> getShape() const {
if (values.empty())
return std::make_pair(0, 0);
return std::make_pair(values.size(), values.front().size());
}
std::vector<T>& operator [] (const int r) {
return values[r];
}
const std::vector<T>& operator [] (const int r) const {
return values[r];
}
friend Matrix operator * (const Matrix &a, const Matrix &b) {
const auto [n, m] = a.getShape();
const auto [p, k] = b.getShape();
assert(m == p);
Matrix result(n, k);
for (int i = 0, j, z; i < n; ++i)
for (j = 0; j < p; ++j)
for (z = 0; z < m; ++z)
result[i][j] = computeAddition(result[i][j], computeMultiplication(a[i][z], b[z][j]));
return result;
}
friend Matrix operator + (Matrix a, const Matrix &b) {
const auto [n, m] = a.getShape();
for (int x = 0, y; x < n; ++x)
for (y = 0; y < m; ++y)
a[x][y] = computeAddition(a[x][y], b[x][y]);
return a;
}
friend Matrix operator - (Matrix a, const Matrix &b) {
const auto [n, m] = a.getShape();
for (int x = 0, y; x < n; ++x)
for (y = 0; y < m; ++y)
a[x][y] = computeSubtraction(a[x][y], b[x][y]);
return a;
}
friend Matrix& operator *= (Matrix &a, const Matrix &b) {
a = a * b;
return a;
}
int getNumberOfRows() const {
return values.size();
}
int getNumberOfColumns() const {
if (values.empty())
return 0;
return values.front().size();
}
static Matrix findPower(Matrix base, long long exponential) {
const int n = base.getNumberOfRows();
Matrix result = getIdentityMatrix(n);
for (; exponential; exponential >>= 1, base *= base)
if (exponential & 1)
result *= base;
return result;
}
bool checkEmpty() const {
return values.empty();
}
bool checkNonEmpty() const {
return !values.empty();
}
void swapRows(const int u, const int v) {
for (int y = getNumberOfColumns() - 1; y >= 0; --y)
swap(values[u][y], values[v][y]);
}
friend std::ostream& operator << (std::ostream &outputStream, const Matrix &m) {
if (m.values.empty())
return outputStream << "[]";
outputStream << "[\n";
for (const auto &row : m.values) {
outputStream << '[';
if (!row.empty()) {
const int length = row.size();
outputStream << std::setw(20) << row.front();
for (int i = 1; i < length; ++i)
outputStream << ',' << std::setw(20) << row[i];
}
outputStream << "]\n";
}
return outputStream << ']';
}
};
using namespace std;
constexpr int MAX_N = 1003, MAX_M = 1003, BASE = 277, MOD = 1E9 + 9999, MAX_2N = 2003, MAX_2M = 2003, MAX_4MN = 4E6 + 6;
int computeMultiplication(const long long x, const long long y) {
return x * y % MOD;
}
int& setMultiplied(int &x, const long long y) {
return x = x * y % MOD;
}
int& setAdded(int &x, const int y) {
if ((x += y) >= MOD)
x -= MOD;
return x;
}
int& setSubtracted(int &x, const int y) {
if ((x += y) < 0)
x += MOD;
return x;
}
int computeAddition(int x, const int y) {
if ((x += y) >= MOD)
x -= MOD;
return x;
}
int computeSubtraction(int x, const int y) {
if ((x += y) < 0)
x += MOD;
return x;
}
int n = 4E6, m;
string image[MAX_2N];
pair<int, int> result(1, 1);
signed N, M, row[MAX_2N][MAX_2M], power[MAX_4MN], h[MAX_2M][MAX_2N];
signed query(const int h[], const int l, const int r) {
return computeSubtraction(h[r], computeMultiplication(h[l - 1], power[r - l + 1]));
}
signed query(const int y, const int l, const int r) {
return computeSubtraction(h[y][r], computeMultiplication(h[y][l - 1], power[(l - 1) * m]));
}
bool checkSmaller(const int x1, const int y1, const int x2, const int y2) {
int low = 0, high = m + 1, middle;
for (; low + 1 < high;) {
middle = low + high >> 1;
if (query(row[x1], y1, y1 + middle - 1) == query(row[x2], y2, y2 + middle - 1))
low = middle;
else
high = middle;
}
return low < m && image[x1 - 1][y1 - 1 + low] < image[x2 - 1][y2 - 1 + low];
}
bool inspectSmaller(const int x1, const int y1, const int x2, const int y2) {
int low = 0, high = n + 1, middle;
for (; low + 1 < high;) {
middle = low + high >> 1;
if (query(y1, x1, x1 + middle - 1) == query(y2, x2, x2 + middle - 1))
low = middle;
else
high = middle;
}
return low < n && checkSmaller(x1 + low, y1, x2 + low, y2);
}
signed main() {
#ifdef LOCAL
freopen("input.INP", "r", stdin);
#endif // LOCAL
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
power[0] = 1;
for (int i = 1; i <= n; ++i)
power[i] = computeMultiplication(power[i - 1], BASE);
cin >> n >> m;
N = n << 1;
M = m << 1;
for (int x = 0, y; x < n; ++x) {
cin >> image[x];
image[x] += image[x];
image[x + n] = image[x];
for (y = 0; y < m; ++y)
row[x + 1][y + 1] = row[x + 1][y + m + 1] = image[x][y];
for (y = 1; y <= M; ++y) {
setAdded(row[x + 1][y], computeMultiplication(row[x + 1][y - 1], BASE));
row[x + 1 + n][y] = row[x + 1][y];
}
}
for (int x = 1, y; x <= N; ++x)
for (y = 1; y <= m; ++y)
h[y][x] = computeAddition(query(row[x], y, y + m - 1), computeMultiplication(h[y][x - 1], power[m]));
for (int x = 1, y; x <= n; ++x)
for (y = 1; y <= m; ++y)
if (inspectSmaller(x, y, result.first, result.second))
result = make_pair(x, y);
for (int x = 0, y; x < n; ++x) {
for (y = 0; y < m; ++y)
cout << image[result.first + x - 1][result.second + y - 1];
cout << '\n';
}
return 0;
}
Compilation message
Main.cpp: In static member function 'static int SignedBigInteger::getReversedBits(int, int)':
Main.cpp:96:38: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
96 | result |= 1 << n - 1 - i;
| ~~~~~~^~~
Main.cpp: In function 'bool checkSmaller(int, int, int, int)':
Main.cpp:919:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
919 | middle = low + high >> 1;
| ~~~~^~~~~~
Main.cpp: In function 'bool inspectSmaller(int, int, int, int)':
Main.cpp:931:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
931 | middle = low + high >> 1;
| ~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
