Submission #434145


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;
}
 
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 << 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 2378 Byte
Status WA
Exec Time 5034 ms
Memory 928 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 0 / 70
Status
AC × 4
AC × 19
AC × 19
WA × 9
TLE × 1
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 25 ms 800 KB
sample-02.txt AC 27 ms 800 KB
sample-03.txt AC 25 ms 924 KB
sample-04.txt AC 26 ms 796 KB
test-1-01.txt AC 26 ms 800 KB
test-1-02.txt AC 25 ms 920 KB
test-1-03.txt AC 26 ms 924 KB
test-1-04.txt AC 25 ms 924 KB
test-1-05.txt AC 25 ms 928 KB
test-1-06.txt AC 27 ms 928 KB
test-1-07.txt AC 27 ms 804 KB
test-1-08.txt AC 27 ms 800 KB
test-1-09.txt AC 25 ms 928 KB
test-1-10.txt AC 25 ms 812 KB
test-1-11.txt AC 23 ms 928 KB
test-1-12.txt AC 27 ms 804 KB
test-1-13.txt AC 26 ms 800 KB
test-1-14.txt AC 27 ms 928 KB
test-1-15.txt AC 27 ms 920 KB
test-2-01.txt WA 26 ms 924 KB
test-2-02.txt WA 26 ms 800 KB
test-2-03.txt TLE 5034 ms 828 KB
test-2-04.txt WA 26 ms 924 KB
test-2-05.txt WA 26 ms 792 KB
test-2-06.txt WA 25 ms 924 KB
test-2-07.txt WA 26 ms 928 KB
test-2-08.txt WA 28 ms 928 KB
test-2-09.txt WA 26 ms 800 KB
test-2-10.txt WA 33 ms 848 KB