Submission #3978499
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; const ull mod = 1e9 + 7; #define REP(i,n) for(int i=0;i<(int)n;++i) //debug #define dump(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; template < typename T > void vprint(T &v){ REP(i, v.size()){ cout << v[i] << " "; } cout << endl; } ll dp[1<<25]; ll x[25], pos[25]; void print_state(ll state){ REP(i, 5){ REP(j, 5){ cout << (state>>(5*i+j) & 1) << " "; } cout << endl; } return; } bool check(ll state, ll rc){ int r = rc/5; int c = rc%5; bool flag1 = (r==0||r==4); bool flag2 = (c==0||c==4); bool res; if(flag1 && flag2){ res = true; } if(!flag1 && flag2){ bool ue = (state>>(rc-5) & 1); bool shita = (state>>(rc+5) & 1); res = !(ue^shita); } if(flag1 && !flag2){ bool hidari = (state>>(rc-1) & 1); bool migi = (state>>(rc+1) & 1); res = !(hidari^migi); } if(!flag1 && !flag2){ bool ue = (state>>(rc-5) & 1); bool shita = (state>>(rc+5) & 1); bool hidari = (state>>(rc-1) & 1); bool migi = (state>>(rc+1) & 1); res = (!(hidari^migi) && !(ue^shita)); } return res; } ll rec(ll state, ll next){ if(dp[state]>=0) return dp[state]; if(next==26) return 1; ll res = 0; if(pos[next]==-1){ REP(i, 25){ if(state>>i & 1) continue; if(x[i]>0) continue; if(check(state, i)){ res += rec(state + (1<<i), next+1); res %= mod; } } }else{ if(check(state, pos[next])){ res += rec(state + (1<<pos[next]), next+1); res %= mod; } } /* cout << next << endl; print_state(state); cout << res << endl; cout << endl; */ dp[state] = res; return res; } int main(){ REP(i, 25) cin >> x[i]; REP(i, 25) pos[i] = -1; REP(i, 25){ if(x[i]==0) continue; pos[x[i]] = i; } REP(i, 1<<25) dp[i] = -1; ll res = rec(0, 1); cout << res << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 25個の整数 |
User | theory_and_me |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2139 Byte |
Status | MLE |
Exec Time | 186 ms |
Memory | 262400 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | MLE | 83 ms | 262400 KB |
sample-02.txt | MLE | 84 ms | 262400 KB |
sample-03.txt | MLE | 83 ms | 262400 KB |
sample-04.txt | MLE | 84 ms | 262400 KB |
test-1-01.txt | MLE | 84 ms | 262400 KB |
test-1-02.txt | MLE | 84 ms | 262400 KB |
test-1-03.txt | MLE | 84 ms | 262400 KB |
test-1-04.txt | MLE | 84 ms | 262400 KB |
test-1-05.txt | MLE | 84 ms | 262400 KB |
test-1-06.txt | MLE | 84 ms | 262400 KB |
test-1-07.txt | MLE | 85 ms | 262400 KB |
test-1-08.txt | MLE | 84 ms | 262400 KB |
test-1-09.txt | MLE | 84 ms | 262400 KB |
test-1-10.txt | MLE | 84 ms | 262400 KB |
test-1-11.txt | MLE | 86 ms | 262400 KB |
test-1-12.txt | MLE | 84 ms | 262400 KB |
test-1-13.txt | MLE | 83 ms | 262400 KB |
test-1-14.txt | MLE | 84 ms | 262400 KB |
test-1-15.txt | MLE | 83 ms | 262400 KB |
test-2-01.txt | MLE | 84 ms | 262400 KB |
test-2-02.txt | MLE | 85 ms | 262400 KB |
test-2-03.txt | MLE | 84 ms | 262400 KB |
test-2-04.txt | MLE | 85 ms | 262400 KB |
test-2-05.txt | MLE | 88 ms | 262400 KB |
test-2-06.txt | MLE | 161 ms | 262400 KB |
test-2-07.txt | MLE | 138 ms | 262400 KB |
test-2-08.txt | MLE | 142 ms | 262400 KB |
test-2-09.txt | MLE | 124 ms | 262400 KB |
test-2-10.txt | MLE | 186 ms | 262400 KB |