Submission #80607

#TimeUsernameProblemLanguageResultExecution timeMemory
80607dualityBoard (CEOI13_board)C++11
100 / 100
17 ms4184 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 ---------- vpii A,B; vi A2,B2; int convert(string a,vpii &A) { int i; A.pb(mp(1,1)); for (i = 0; i < a.size(); i++) { if (a[i] == '1') { if (A.back().first == 0) A.back().second++; else A.pb(mp(0,1)); } else if (a[i] == '2') { if (A.back().first == 1) A.back().second++; else A.pb(mp(1,1)); } else if (a[i] == 'U') { A.back().second--; if (A.back().second == 0) A.pop_back(); } else if (a[i] == 'L') { if (A.back().first == 1) { A.back().second--; if (A.back().second == 0) A.pop_back(),A.back().second++; else A.pb(mp(0,1)); } else { pii p = A.back(); A.pop_back(); A.back().second--; if (A.back().second == 0) A.pop_back(),A.back().second++; else A.pb(mp(0,1)); A.pb(mp(1,p.second)); } } else { if (A.back().first == 0) { A.back().second--; if (A.back().second == 0) A.pop_back(),A.back().second++; else A.pb(mp(1,1)); } else { pii p = A.back(); A.pop_back(); A.back().second--; if (A.back().second == 0) A.pop_back(),A.back().second++; else A.pb(mp(1,1)); A.pb(mp(0,p.second)); } } } return 0; } int main() { string a,b; cin >> a >> b; int i; convert(a,A),convert(b,B); for (i = 0; i < A.size(); i++) { while (A[i].second > 0) A2.pb(A[i].first),A[i].second--; } for (i = 0; i < B.size(); i++) { while (B[i].second > 0) B2.pb(B[i].first),B[i].second--; } int ans = A2.size()+B2.size()-2,x = 0; if (A2.size() < B2.size()) swap(A2,B2); while (A2.size() > B2.size()) x++,A2.pop_back(); for (i = 0; i < A2.size(); i++) { if (A2[i] != B2[i]) { if (A2[i] < B2[i]) swap(A2,B2); break; } } int s = 0; for (i = 0; i < A2.size(); i++) { s <<= 1,s += A2[i]-B2[i]; if (s > ans) break; else ans = min(ans,s+x+2*((int) A2.size()-i-1)); } printf("%d\n",ans); return 0; }

Compilation message (stderr)

board.cpp: In function 'int convert(std::__cxx11::string, vpii&)':
board.cpp:63:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < a.size(); i++) {
                 ~~^~~~~~~~~~
board.cpp: In function 'int main()':
board.cpp:115:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < A.size(); i++) {
                 ~~^~~~~~~~~~
board.cpp:118:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < B.size(); i++) {
                 ~~^~~~~~~~~~
board.cpp:125:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < A2.size(); i++) {
                 ~~^~~~~~~~~~~
board.cpp:132:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < A2.size(); i++) {
                 ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...