| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 320728 |
2020-11-09T16:00:16 Z |
monus1042 |
Board (CEOI13_board) |
C++17 |
|
200 ms |
1936 KB |
// NK
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
typedef pair<int,int> ii;
typedef int ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define psf push_front
#define pof pop_front
#define mkp make_pair
#define mkt make_tuple
#define all(x) x.begin(), x.end()
#define Bolivia_is_nice ios::sync_with_stdio(false), cin.tie(nullptr)
//typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ord_set;
int MAXS;
string unit;
string sum(string a, string b){
string r(a.size(), '0');
char carry = '0';
for (int i=0; i<a.size(); i++){
short c1 = 0;
if (a[i] == '1') c1++;
if (b[i] == '1') c1++;
if (carry == '1') c1++;
if (c1 == 1 || c1 == 3) r[i] = '1';
if (c1 >= 2) carry = '1';
else carry = '0';
}
return r;
}
string mult(string a){
string r(a.size(), '0');
for (int i=0; i<a.size() - 1; i++){
if (a[i] == '1') r[i+1] = '1';
}
return r;
}
string divi(string a){
string r(a.size(), '0');
for (int i=1; i<a.size(); i++){
if (a[i] == '1') r[i-1] = '1';
}
return r;
}
string complem(string a){
string r(a.size(), '0');
for (int i=0; i<a.size(); i++){
if (a[i] == '1') r[i] = '0';
else r[i] = '1';
}
return r;
}
string sub(string a, string b){
string aux = complem(b);
a = sum(a, aux);
a = sum(a, unit);
return a;
}
string locationof(string s, string nod, string & lev){
for (int i=0; i<s.size(); i++){
if (s[i] == '1'){
nod = mult(nod);
lev = sum(lev, unit);
}else if (s[i] == '2'){
nod = mult(nod);
nod = sum(nod, unit);
lev = sum(lev, unit);
}else if (s[i] == 'U'){
nod = divi(nod);
lev = sub(lev, unit);
}else if (s[i] == 'L'){
nod = sub(nod, unit);
}else{ // R
nod = sum(nod, unit);
}
}
return nod;
}
void solve(){
string a,b; cin>>a>>b;
int maxi = max(a.size(), b.size());
MAXS = maxi+11;
unit.resize(MAXS, '0');
string AL (MAXS, '0'), BL (MAXS, '0');
unit[0] = '1';
string A = locationof(a, unit, AL), B = locationof(b, unit, BL);
string auxa(AL), auxb(BL);
reverse(all(auxa)); reverse(all(auxb));
if (auxa < auxb){
swap(AL, BL);
swap(A, B);
}
string diff = sub(AL, BL);
ll num = 0;
for (ll i=0; i<31; i++){
if (diff[i] == '1'){
num += (1 << i);
}
}
for (ll i=0; i<num; i++){
AL = sub(AL, unit);
A = divi(A);
}
///
string ans(MAXS, '1');
auxa = A, auxb = B;
reverse(all(auxa)); reverse(all(auxb));
if (auxa > auxb) swap(A, B);
string acc(MAXS, '0');
while(1){
bool ok = 0;
for (int i=0; i<MAXS; i++){
if (A[i] == '1') ok = 1;
}
if (!ok) break;
string current = diff;
string HOR = sub(B, A);
current = sum(current, HOR);
current = sum(current, acc);
reverse(all(current));
ans = min(ans, current);
// lift:
acc = sum(acc, unit);
acc = sum(acc, unit);
A = divi(A);
B = divi(B);
}
reverse(all(ans));
ll Answer = 0;
for (ll i=0; i<31; i++){
if (ans[i] == '1'){
Answer += (1 << i);
}
}
cout<<Answer<<'\n';
}
int main(){
Bolivia_is_nice;
int t = 1; //cin>>t;
while(t--)
solve();
return 0;
}
/*
~/.emacs
*/
Compilation message
board.cpp: In function 'std::string sum(std::string, std::string)':
board.cpp:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int i=0; i<a.size(); i++){
| ~^~~~~~~~~
board.cpp: In function 'std::string mult(std::string)':
board.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i=0; i<a.size() - 1; i++){
| ~^~~~~~~~~~~~~
board.cpp: In function 'std::string divi(std::string)':
board.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i=1; i<a.size(); i++){
| ~^~~~~~~~~
board.cpp: In function 'std::string complem(std::string)':
board.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int i=0; i<a.size(); i++){
| ~^~~~~~~~~
board.cpp: In function 'std::string locationof(std::string, std::string, std::string&)':
board.cpp:80:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i=0; i<s.size(); i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1097 ms |
1472 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1064 ms |
892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
689 ms |
740 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1053 ms |
924 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1084 ms |
1652 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
1936 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
1656 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
