Submission #7067785


Source Code Expand

#include <bits/stdc++.h>

template <typename Sequence>
std::vector<int> manacher(const Sequence& sequence)
{
	std::vector<int> table(sequence.size());
	int center{}, length{};
	while (center < (int)sequence.size())
	{
		while (center - length >= 0 && center + length < (int)sequence.size() && sequence[center - length] == sequence[center + length])
			length++;
		table[center] = length;
		int diff{1};
		while (center - diff >= 0 && center + diff < (int)sequence.size() && table[center - diff] + diff < length)
		{
			table[center + diff] = table[center - diff];
			diff++;
		}
		center += diff;
		length -= diff;
	}
	return std::move(table);
}

int main()
{
	int M, N;
	scanf("%d%d", &M, &N);
	std::vector<int> row(2 * M - 1), column(2 * N - 1);
	for (int i{1}; i < 2 * M - 1; i += 2)
		row[i] = -1;
	for (int i{1}; i < 2 * N - 1; i += 2)
		column[i] = -1;
	for (int i{}; i < 2 * M - 1; i += 2)
		for (int j{}; j < 2 * N - 1; j += 2)
		{
			char tmp;
			scanf(" %c", &tmp);
			if (tmp == '1')
			{
				row[i]++;
				column[j]++;
			}
		}
	std::vector<int> rowRot(manacher(row)), columnRot(manacher(column));
	int64_t row_count{}, column_count{};
	for (int border{1}; border < (int)rowRot.size(); border += 2)
	{
		int top{(border + -1) / 2}, bottom{(border + (int)rowRot.size()) / 2};
		if (top - rowRot[top] == -1 && bottom + rowRot[bottom] == (int)rowRot.size())
			row_count++;
	}
	for (int border{1}; border < (int)columnRot.size(); border += 2)
	{
		int left{(border + -1) / 2}, right{(border + (int)columnRot.size()) / 2};
		if (left - columnRot[left] == -1 && right + columnRot[right] == (int)columnRot.size())
			column_count++;
	}
	printf("%lld\n", row_count * column_count);

	return 0;
}

Submission Info

Submission Time
Task E - Artist
User TanakaTaroh
Language C++14 (GCC 5.4.1)
Score 200
Code Size 1761 Byte
Status AC
Exec Time 24 ms
Memory 1792 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:59:43: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int64_t {aka long int}’ [-Wformat=]
  printf("%lld\n", row_count * column_count);
                                           ^
./Main.cpp:28:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &M, &N);
                       ^
./Main.cpp:38:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &tmp);
                      ^

Judge Result

Set Name All
Score / Max Score 200 / 200
Status
AC × 34
Set Name Test Cases
All 0-sample1, 0-sample2, 0-sample3, 1-random-small-0, 1-random-small-1, 1-random-small-2, 1-random-small-3, 1-random-small-4, 2-random-large-0, 2-random-large-1, 2-random-large-2, 2-random-large-3, 2-random-large-4, 3-random-tsubasa-0, 3-random-tsubasa-1, 3-random-tsubasa-2, 3-random-tsubasa-3, 3-random-tsubasa-4, 3-random-tsubasa-5, 3-random-tsubasa-6, 3-random-tsubasa-7, 3-random-tsubasa-8, 3-random-tsubasa-9, 8-hand-small1, 8-hand-small2, 8-hand-small3, 9-hand-large1, 9-hand-large2, 9-hand-large3, 9-hand-large4, 9-hand-large5, 9-hand-large6, 9-hand-large7, 9-hand-large8
Case Name Status Exec Time Memory
0-sample1 AC 1 ms 256 KB
0-sample2 AC 1 ms 256 KB
0-sample3 AC 1 ms 256 KB
1-random-small-0 AC 1 ms 256 KB
1-random-small-1 AC 1 ms 256 KB
1-random-small-2 AC 1 ms 256 KB
1-random-small-3 AC 1 ms 256 KB
1-random-small-4 AC 1 ms 256 KB
2-random-large-0 AC 3 ms 256 KB
2-random-large-1 AC 2 ms 256 KB
2-random-large-2 AC 3 ms 256 KB
2-random-large-3 AC 2 ms 256 KB
2-random-large-4 AC 2 ms 256 KB
3-random-tsubasa-0 AC 10 ms 1408 KB
3-random-tsubasa-1 AC 24 ms 1664 KB
3-random-tsubasa-2 AC 16 ms 1664 KB
3-random-tsubasa-3 AC 20 ms 1664 KB
3-random-tsubasa-4 AC 20 ms 1664 KB
3-random-tsubasa-5 AC 24 ms 1664 KB
3-random-tsubasa-6 AC 24 ms 1280 KB
3-random-tsubasa-7 AC 12 ms 1792 KB
3-random-tsubasa-8 AC 14 ms 1280 KB
3-random-tsubasa-9 AC 18 ms 1536 KB
8-hand-small1 AC 1 ms 256 KB
8-hand-small2 AC 1 ms 256 KB
8-hand-small3 AC 1 ms 256 KB
9-hand-large1 AC 7 ms 1024 KB
9-hand-large2 AC 12 ms 1792 KB
9-hand-large3 AC 12 ms 1792 KB
9-hand-large4 AC 12 ms 1792 KB
9-hand-large5 AC 23 ms 256 KB
9-hand-large6 AC 23 ms 256 KB
9-hand-large7 AC 6 ms 896 KB
9-hand-large8 AC 9 ms 1280 KB