AtCoder Beginner Contest 025

Submission #1758702

Source codeソースコード

#include <bits/stdc++.h>
typedef long long int ll;
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define EREP(i, n) for (int i = (n - 1); i >= 0; --i)
#define mod 1000000007
#define INF 93193111451418101
#define MIN -93193111451418101
//#define INF 931931114518101
using namespace std;
typedef pair<ll, ll> P;
template <typename T> void fill_all(T &arr, const T &v) { arr = v; }
template <typename T, typename ARR> void fill_all(ARR &arr, const T &v) {
  for (auto &i : arr) {
    fill_all(i, v);
  }
}
#define yo 100001
//------------------変数-----------------------//
ll grid[26];
int dp[1 << 25];
map<ll, ll> selected;
//-------------------関数----------------------//

int main() {
  REP(i, 25) {
    cin >> grid[i];
    if (grid[i]) {
      selected[grid[i]] = i + 1;
    }
  }
  dp[0] = 1;
  REP(i, (1 << 25) - 1) {
    if (!dp[i])
      continue;
    ll flagcnt = __builtin_popcount(i) + 1; //どの整数まで数えたか
    if (selected[flagcnt]) {
      ll x = selected[flagcnt] - 1;
      ll y = x / 5;
      x %= 5;
      ll place = selected[flagcnt] - 1;
      if (x > 0 && x < 4 && ((i >> (place - 1)) ^ (i >> (place + 1))) & 1)
        continue;
      if (y > 0 && y < 4 && ((i >> (place - 5)) ^ (i >> (place + 5))) & 1)
        continue;
      (dp[i | (1 << place)] += dp[i]) %= mod;
    } else {
      REP(j, 25) {
        if (grid[j] || i >> j & 1) {
          continue;
        }
        ll x = j;
        ll y = x / 5;
        x %= 5;
        ll place = j;
        if (x > 0 && x < 4 && ((i >> (place - 1)) ^ (i >> (place + 1))) & 1)
          continue;
        if (y > 0 && y < 4 && ((i >> (place - 5)) ^ (i >> (place + 5))) & 1)
          continue;
        (dp[i | (1 << place)] += dp[i]) %= mod;
      }
    }
  }
  cout << dp[(1 << 25) - 1] << endl;
  ;
  return 0;
}

Submission

Task問題 D - 25個の整数
User nameユーザ名 keidaroo
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1903 Byte
File nameファイル名
Exec time実行時間 97 ms
Memory usageメモリ使用量 113280 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample-01.txt,sample-02.txt,sample-03.txt,sample-04.txt
Subtask1 30 / 30 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 70 / 70 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample-01.txt AC 26 ms 12544 KB
sample-02.txt AC 27 ms 20736 KB
sample-03.txt AC 23 ms 256 KB
sample-04.txt AC 26 ms 12544 KB
test-1-01.txt AC 26 ms 12544 KB
test-1-02.txt AC 26 ms 14592 KB
test-1-03.txt AC 27 ms 16640 KB
test-1-04.txt AC 37 ms 69888 KB
test-1-05.txt AC 27 ms 16640 KB
test-1-06.txt AC 27 ms 16640 KB
test-1-07.txt AC 24 ms 2304 KB
test-1-08.txt AC 31 ms 39168 KB
test-1-09.txt AC 26 ms 12544 KB
test-1-10.txt AC 26 ms 12544 KB
test-1-11.txt AC 26 ms 12544 KB
test-1-12.txt AC 27 ms 18688 KB
test-1-13.txt AC 26 ms 12544 KB
test-1-14.txt AC 27 ms 18688 KB
test-1-15.txt AC 28 ms 24832 KB
test-2-01.txt AC 31 ms 33024 KB
test-2-02.txt AC 29 ms 24960 KB
test-2-03.txt AC 30 ms 30976 KB
test-2-04.txt AC 48 ms 113152 KB
test-2-05.txt AC 42 ms 70272 KB
test-2-06.txt AC 77 ms 68224 KB
test-2-07.txt AC 66 ms 92544 KB
test-2-08.txt AC 83 ms 113280 KB
test-2-09.txt AC 70 ms 74624 KB
test-2-10.txt AC 97 ms 78336 KB