Submission #782906

#TimeUsernameProblemLanguageResultExecution timeMemory
782906RecursiveCoBoard (CEOI13_board)C++14
10 / 100
172 ms262144 KiB
// CF template, version 3.0 #include <bits/stdc++.h> using namespace std; #define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0) #define getTest int t; cin >> t #define eachTest for (int _var=0;_var<t;_var++) #define get(name) int (name); cin >> (name) #define out(o) cout << (o) #define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); } #define sortl(name) sort((name).begin(), (name).end()) #define rev(name) reverse((name).begin(), (name).end()) #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++) #define decision(b) if (b){out("YES");}else{out("NO");} #define int long long vector<int> compress(string s) { stack<pair<int, int>> sst; int n = s.size(); int len, el, lenbefore, bfbf; forto(n, i) { switch (s[i]) { case '1': if (sst.empty() || sst.top().first == 2) sst.push({1, 1}); else { len = sst.top().second; sst.pop(); sst.push({1, len + 1}); } break; case '2': if (sst.empty() || sst.top().first == 1) sst.push({2, 1}); else { len = sst.top().second; sst.pop(); sst.push({2, len + 1}); } break; case 'U': len = sst.top().second; el = sst.top().first; sst.pop(); if (len != 1) sst.push({el, len - 1}); break; case 'L': el = sst.top().first; len = sst.top().second; if (el == 2) { sst.pop(); if (len != 1) { sst.push({2, len - 1}); sst.push({1, 1}); } else { lenbefore = sst.top().second; sst.pop(); sst.push({1, lenbefore + 1}); } } else { sst.pop(); lenbefore = sst.top().second; if (lenbefore != 1) { sst.pop(); sst.push({2, lenbefore - 1}); sst.push({1, 1}); sst.push({2, len}); } else { sst.pop(); if (sst.empty()) { sst.push({1, 1}); sst.push({2, len}); } else { bfbf = sst.top().second; sst.pop(); sst.push({1, bfbf + 1}); sst.push({2, len}); } } } break; case 'R': el = sst.top().first; len = sst.top().second; if (el == 1) { sst.pop(); if (len != 1) { sst.push({1, len - 1}); sst.push({2, 1}); } else { lenbefore = sst.top().second; sst.pop(); sst.push({2, lenbefore + 1}); } } else { sst.pop(); lenbefore = sst.top().second; if (lenbefore != 1) { sst.pop(); sst.push({1, lenbefore - 1}); sst.push({2, 1}); sst.push({1, len}); } else { sst.pop(); if (sst.empty()) { sst.push({2, 1}); sst.push({1, len}); } else { bfbf = sst.top().second; sst.pop(); sst.push({2, bfbf + 1}); sst.push({1, len}); } } } break; } } vector<int> res; while (!sst.empty()) { int ele = sst.top().first; int leng = sst.top().second; forto(leng, i) res.push_back(ele); sst.pop(); } rev(res); return res; } signed main() { improvePerformance; //getTest; //eachTest { string s, t; cin >> s; cin >> t; vector<int> S = compress(s); vector<int> T = compress(t); if (S > T) swap(S, T); int slev = S.size(); int tlev = T.size(); vector<int> moves; int cnt = 0; forto(min(slev, tlev), i) { if (S[i] == T[i]) cnt *= 2; else if (S[i] == 1) cnt = cnt * 2 + 1; else cnt = cnt * 2 - 1; if (cnt > 250000) break; moves.push_back(cnt); } int ans = slev + tlev; forto(moves.size(), i) ans = min(ans, slev - i + tlev - i + moves[i] - 2); out(ans); //} }

Compilation message (stderr)

board.cpp: In function 'std::vector<long long int> compress(std::string)':
board.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
board.cpp:24:5: note: in expansion of macro 'forto'
   24 |     forto(n, i) {
      |     ^~~~~
board.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
board.cpp:124:9: note: in expansion of macro 'forto'
  124 |         forto(leng, i) res.push_back(ele);
      |         ^~~~~
board.cpp: In function 'int main()':
board.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
board.cpp:146:9: note: in expansion of macro 'forto'
  146 |         forto(min(slev, tlev), i) {
      |         ^~~~~
board.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
board.cpp:154:9: note: in expansion of macro 'forto'
  154 |         forto(moves.size(), i) ans = min(ans, slev - i + tlev - i + moves[i] - 2);
      |         ^~~~~
board.cpp:15:52: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                              ~~~~~~^~~~~~~~
board.cpp:154:9: note: in expansion of macro 'forto'
  154 |         forto(moves.size(), i) ans = min(ans, slev - i + tlev - i + moves[i] - 2);
      |         ^~~~~
#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...