Submission #231805

#TimeUsernameProblemLanguageResultExecution timeMemory
231805dualityRuins 3 (JOI20_ruins3)C++11
6 / 100
2372 ms304112 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- #define MOD 1000000007 int A[600]; vpii dp; int temp[1 << 26]; int main() { int i; int N; scanf("%d",&N); for (i = 0; i < N; i++) scanf("%d",&A[i]),A[i]--; int j,k,l,p; dp.pb(mp(1,1)); for (i = 1; i < N; i++) { for (j = 0; j < dp.size(); j++) { for (k = 0; k < 2*i+1; k++) { for (l = k; l < 2*i+1; l++) { int a = dp[j].first & ((1 << k)-1); int b = (dp[j].first >> k) & ((1 << (l-k))-1); int c = dp[j].first >> l; int m = a | (b << (k+1)) | (c << (l+2)); for (p = 0; p <= k; p++) { if (!(m & (1 << p))) { m |= (1 << p); break; } } temp[m] += dp[j].second; if (temp[m] >= MOD) temp[m] -= MOD; } } } dp.clear(); for (j = 0; j < (1 << (2*(i+1))); j++) { if (temp[j] > 0) dp.pb(mp(j,temp[j])),temp[j] = 0; } } int ans = 0,m = 0; for (i = 0; i < N; i++) m |= (1 << (2*N-1-A[i])); for (i = 0; i < dp.size(); i++) { if (dp[i].first == m) { ans += dp[i].second; if (ans >= MOD) ans -= MOD; } } printf("%d\n",ans); return 0; }

Compilation message (stderr)

ruins3.cpp: In function 'int main()':
ruins3.cpp:71:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < dp.size(); j++) {
                     ~~^~~~~~~~~~~
ruins3.cpp:96:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < dp.size(); i++) {
                 ~~^~~~~~~~~~~
ruins3.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
ruins3.cpp:66:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < N; i++) scanf("%d",&A[i]),A[i]--;
                             ~~~~~~~~~~~~~~~~~^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...