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 |
|
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 |