QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#34299 | #4195. Looking for Waldo | sinbad# | WA | 2ms | 3652kb | C++17 | 5.2kb | 2022-06-06 20:31:04 | 2022-06-06 20:31:06 |
Judging History
answer
// #define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const multiset<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
template <class T> auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D> auto vect(const T& v, int n, D... m) {
return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}
using int64 = long long;
using int128 = __int128_t;
using ii = pair<int, int>;
#define SZ(x) (int)((x).size())
template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
// mt19937 mrand(random_device{}());
// int rnd(int x) { return mrand() % x; }
mt19937_64 mrand(random_device{}());
int64 rnd(int64 x) { return mrand() % x; }
int lg2(int64 x) { return sizeof(int64) * 8 - 1 - __builtin_clzll(x); }
template <class T> void out(const vector<T>& a) { for (int i = 0; i < SZ(a); ++i) cout << a[i] << " \n"[i + 1 == SZ(a)]; }
template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> void dedup(vector<T>& v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); }
void add_mod(int& x, int y) { x += y; if (x >= MOD) x -= MOD; }
void sub_mod(int& x, int y) { x += MOD - y; if (x >= MOD) x -= MOD; }
struct fast_ios {
fast_ios() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
};
} fast_ios_;
int main() {
int n, m;
cin >> n >> m;
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
if (n > m) {
vector<string> t(m, string(n, ' '));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) t[j][i] = s[i][j];
}
s = t;
}
string S = "WALDO";
int ret = inf<int>;
auto solve =
[&](const vector<int>& a) {
int n = SZ(a), ret = inf<int>;
vector<int> cnt(5);
for (int i = 0, j; i < n; ++i) {
if (i == 0) {
for (j = 0; j < n && !(cnt[0] && cnt[1] && cnt[2] && cnt[3] && cnt[4]); ++j) {
for (int k = 0; k < 5; ++k) cnt[k] += (a[j] >> k) & 1;
}
} else {
for (int k = 0; k < 5; ++k) cnt[k] -= (a[i - 1] >> k) & 1;
for (; j < n && !(cnt[0] && cnt[1] && cnt[2] && cnt[3] && cnt[4]); ++j) {
for (int k = 0; k < 5; ++k) cnt[k] += (a[j] >> k) & 1;
}
}
if (cnt[0] && cnt[1] && cnt[2] && cnt[3] && cnt[4]) {
ckmin(ret, j - i);
}
}
return ret;
};
for (int i = 0; i < n; ++i) {
vector<int> a(m);
for (int j = i; j < n; ++j) {
for (int k = 0; k < m; ++k) {
int x = S.find(s[j][k]);
if (x != string::npos) a[k] |= 1 << x;
}
int len = solve(a);
trace(i, j, len);
if (len != inf<int>) ckmin(ret, len * (j - i + 1));
}
}
if (ret == inf<int>) {
cout << "impossible" << '\n';
} else {
cout << ret << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3616kb
input:
5 5 ABCDE FGHIJ KLMNO PQRST VWXYZ
output:
25
result:
ok single line: '25'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3540kb
input:
5 10 ABCDEABCDE FGHIJFGHIJ KLMNOKLMNO PQRSTPQRST VWXYZVWXYZ
output:
20
result:
ok single line: '20'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3556kb
input:
5 10 WAALDLODOW AWWLAOODOW LOLADOWALO ADALLLWWOL WWOOAAAALO
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3500kb
input:
2 3 WAL TER
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3556kb
input:
1 260 AWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWLDO
output:
260
result:
ok single line: '260'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
1 5 WALDO
output:
5
result:
ok single line: '5'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
5 5 WXXAL XALDO XDOXX ALXXX DOXXX
output:
9
result:
ok single line: '9'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
7 115 DVGTNMMOMTPGLREEHPNWWOVARKFSSAQNWBBSUIUXDTRLZXHJAVOQPZWNJDMCBJRVSJNTUSOGUYKBWVUEDGJJJZRIJAJONHUSUJVGMYRDNRKZZLYOKRB VVPSQMSDLFLEHIBTFMMRAWJFZTRVXOQJCNMPLYMWAXRXPXQWEDMWYTCQQBDGUACGWIQBIIRMTCYBQPKNWPYIRPHEIFHCPKYTVRSBBXUXVOCSLPJFRWM DUSXXJPYFRNCGGDJPDVDXGKLDBABDGMWBELWYWMQMQCRAHINEYSMTLXGUOBGAC...
output:
8
result:
ok single line: '8'
Test #9:
score: -100
Wrong Answer
time: 2ms
memory: 3572kb
input:
43 6 MSKXQI PGFKAO YZSLPS LVMBUX QQJWVW GWVLPM HDBTRG WKHMGP RLGDEB TXYZEY LQRDJI IFIJZU STLLPN HDJOID NTIAZG KHQVHO UBUERZ PWBOBI UTIEJW KWEPPZ TVWEBQ JVFXYB QHKYCG DXJXMD BZGFOV RRHFKI PZUCBJ NUOPLE ZWVFVP NACTWZ XAJRUG XOBZIC EGHUGF TODGGA AYQHYD QPVLIQ HJLKOV WTRZJJ AXSPON LWRXIG VPUZOR ZDZQXK C...
output:
10
result:
wrong answer 1st lines differ - expected: '11', found: '10'