Submission #434187
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define loop for(;;)
#define trace(var) cerr<<">>> "<<#var<<" = "<<var<<endl;
#define inf (1e9)
#define eps (1e-9)
using Integer = long long;
using Real = long double;
const Real PI = acos(-1);
template<class S, class T> inline
ostream& operator<<(ostream&os, pair<S,T> p) {
return os << '(' << p.first << ", " << p.second << ')';
}
template<class S, class T, class U> inline
ostream& operator<<(ostream&os, tuple<S,T,U> t) {
return os << '('
<< get<0>(t) << ", "
<< get<1>(t) << ", "
<< get<2>(t) << ')';
}
template<class T> inline
ostream& operator<<(ostream&os, vector<T> v) {
if (v.size() == 0) { return os << "(empty)"; }
os << v[0];
for (int i=1, len=v.size(); i<len; ++i) os << ' ' << v[i];
return os;
}
template<class T> inline
istream& operator>>(istream&is, vector<T>&v) {
rep (i, v.size()) is >> v[i];
return is;
}
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };
using vi = vector<int>;
using vvi = vector<vi>;
int f[5][5];
bool mono(int a, int b, int c) {
if (a < b and b < c) return true;
if (a > b and b > c) return true;
return false;
}
bool ok() {
rep (i, 3) {
rep (j, 5) {
if (mono(f[i][j], f[i+1][j], f[i+2][j])) return false;
}
}
rep (i, 5) {
rep (j, 3) {
if (mono(f[i][j], f[i][j+1], f[i][j+2])) return false;
}
}
return true;
}
bool giok() {
rep (i, 3) {
rep (j, 5) {
if (f[i][j] == 0) continue;
if (f[i+1][j] == 0) continue;
if (f[i+2][j] == 0) continue;
if (mono(f[i][j], f[i+1][j], f[i+2][j])) return false;
}
}
rep (i, 5) {
rep (j, 3) {
if (f[i][j] == 0) continue;
if (f[i][j+1] == 0) continue;
if (f[i][j+2] == 0) continue;
if (mono(f[i][j], f[i][j+1], f[i][j+2])) return false;
}
}
return true;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
cout.setf(ios::fixed);
cout.precision(10);
random_device dev;
mt19937 rand(dev());
set<int> s;
rep (i, 25) s.insert(i+1);
rep (i, 5) rep (j, 5) cin >> f[i][j];
rep (i, 5) rep (j, 5) {
if (f[i][j] > 0) s.erase(f[i][j]);
}
vi ar;
for (int x: s) ar.push_back(x);
vector<pair<int, int>> es;
rep (i, 5) rep (j, 5) if (f[i][j] == 0) es.push_back({ i, j });
if (es.size() == 0) {
cout << (ok() ? 1 : 0) << endl;
return 0;
}
if (ar.size() > 12) {
cout << (giok()? 1 : 0) << endl;
return 0;
}
int ans = 0;
do {
rep (i, ar.size()) {
int x = ar[i];
auto p = es[i];
f[p.first][p.second] = x;
}
if (ok()) ++ans;
} while (next_permutation(begin(ar), end(ar)));
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 25個の整数 |
User |
cympfh |
Language |
C++11 (GCC 4.9.2) |
Score |
30 |
Code Size |
2863 Byte |
Status |
WA |
Exec Time |
5033 ms |
Memory |
932 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
0 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
Subtask1 |
sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, test-1-01.txt, test-1-02.txt, test-1-03.txt, test-1-04.txt, test-1-05.txt, test-1-06.txt, test-1-07.txt, test-1-08.txt, test-1-09.txt, test-1-10.txt, test-1-11.txt, test-1-12.txt, test-1-13.txt, test-1-14.txt, test-1-15.txt |
Subtask2 |
sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, test-1-01.txt, test-1-02.txt, test-1-03.txt, test-1-04.txt, test-1-05.txt, test-1-06.txt, test-1-07.txt, test-1-08.txt, test-1-09.txt, test-1-10.txt, test-1-11.txt, test-1-12.txt, test-1-13.txt, test-1-14.txt, test-1-15.txt, test-2-01.txt, test-2-02.txt, test-2-03.txt, test-2-04.txt, test-2-05.txt, test-2-06.txt, test-2-07.txt, test-2-08.txt, test-2-09.txt, test-2-10.txt |
Case Name |
Status |
Exec Time |
Memory |
sample-01.txt |
AC |
24 ms |
796 KB |
sample-02.txt |
AC |
26 ms |
928 KB |
sample-03.txt |
AC |
24 ms |
804 KB |
sample-04.txt |
AC |
24 ms |
800 KB |
test-1-01.txt |
AC |
23 ms |
924 KB |
test-1-02.txt |
AC |
24 ms |
928 KB |
test-1-03.txt |
AC |
22 ms |
800 KB |
test-1-04.txt |
AC |
23 ms |
924 KB |
test-1-05.txt |
AC |
24 ms |
924 KB |
test-1-06.txt |
AC |
24 ms |
928 KB |
test-1-07.txt |
AC |
25 ms |
924 KB |
test-1-08.txt |
AC |
25 ms |
924 KB |
test-1-09.txt |
AC |
25 ms |
924 KB |
test-1-10.txt |
AC |
25 ms |
728 KB |
test-1-11.txt |
AC |
25 ms |
732 KB |
test-1-12.txt |
AC |
26 ms |
920 KB |
test-1-13.txt |
AC |
25 ms |
732 KB |
test-1-14.txt |
AC |
24 ms |
916 KB |
test-1-15.txt |
AC |
27 ms |
732 KB |
test-2-01.txt |
WA |
25 ms |
732 KB |
test-2-02.txt |
WA |
24 ms |
800 KB |
test-2-03.txt |
TLE |
5033 ms |
928 KB |
test-2-04.txt |
WA |
25 ms |
916 KB |
test-2-05.txt |
WA |
24 ms |
916 KB |
test-2-06.txt |
WA |
25 ms |
728 KB |
test-2-07.txt |
WA |
25 ms |
924 KB |
test-2-08.txt |
WA |
24 ms |
920 KB |
test-2-09.txt |
WA |
26 ms |
920 KB |
test-2-10.txt |
WA |
25 ms |
932 KB |